File: | lib/CodeGen/MachineDominators.cpp |
Warning: | line 140, column 1 Potential leak of memory pointed to by 'IsNewIDom.X' |
[?] Use j/k keys for keyboard navigation
1 | //===- MachineDominators.cpp - Machine Dominator Calculation --------------===// | |||
2 | // | |||
3 | // The LLVM Compiler Infrastructure | |||
4 | // | |||
5 | // This file is distributed under the University of Illinois Open Source | |||
6 | // License. See LICENSE.TXT for details. | |||
7 | // | |||
8 | //===----------------------------------------------------------------------===// | |||
9 | // | |||
10 | // This file implements simple dominator construction algorithms for finding | |||
11 | // forward dominators on machine functions. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "llvm/CodeGen/MachineDominators.h" | |||
16 | #include "llvm/ADT/SmallBitVector.h" | |||
17 | #include "llvm/CodeGen/Passes.h" | |||
18 | #include "llvm/Support/CommandLine.h" | |||
19 | ||||
20 | using namespace llvm; | |||
21 | ||||
22 | // Always verify dominfo if expensive checking is enabled. | |||
23 | #ifdef EXPENSIVE_CHECKS | |||
24 | static bool VerifyMachineDomInfo = true; | |||
25 | #else | |||
26 | static bool VerifyMachineDomInfo = false; | |||
27 | #endif | |||
28 | static cl::opt<bool, true> VerifyMachineDomInfoX( | |||
29 | "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden, | |||
30 | cl::desc("Verify machine dominator info (time consuming)")); | |||
31 | ||||
32 | namespace llvm { | |||
33 | template class DomTreeNodeBase<MachineBasicBlock>; | |||
34 | template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase | |||
35 | } | |||
36 | ||||
37 | char MachineDominatorTree::ID = 0; | |||
38 | ||||
39 | INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",static void *initializeMachineDominatorTreePassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "MachineDominator Tree Construction" , "machinedomtree", &MachineDominatorTree::ID, PassInfo:: NormalCtor_t(callDefaultCtor<MachineDominatorTree>), true , true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeMachineDominatorTreePassFlag; void llvm::initializeMachineDominatorTreePass(PassRegistry &Registry ) { llvm::call_once(InitializeMachineDominatorTreePassFlag, initializeMachineDominatorTreePassOnce , std::ref(Registry)); } | |||
40 | "MachineDominator Tree Construction", true, true)static void *initializeMachineDominatorTreePassOnce(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "MachineDominator Tree Construction" , "machinedomtree", &MachineDominatorTree::ID, PassInfo:: NormalCtor_t(callDefaultCtor<MachineDominatorTree>), true , true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeMachineDominatorTreePassFlag; void llvm::initializeMachineDominatorTreePass(PassRegistry &Registry ) { llvm::call_once(InitializeMachineDominatorTreePassFlag, initializeMachineDominatorTreePassOnce , std::ref(Registry)); } | |||
41 | ||||
42 | char &llvm::MachineDominatorsID = MachineDominatorTree::ID; | |||
43 | ||||
44 | void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { | |||
45 | AU.setPreservesAll(); | |||
46 | MachineFunctionPass::getAnalysisUsage(AU); | |||
47 | } | |||
48 | ||||
49 | bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) { | |||
50 | CriticalEdgesToSplit.clear(); | |||
51 | NewBBs.clear(); | |||
52 | DT.reset(new DomTreeBase<MachineBasicBlock>()); | |||
53 | DT->recalculate(F); | |||
54 | return false; | |||
55 | } | |||
56 | ||||
57 | MachineDominatorTree::MachineDominatorTree() | |||
58 | : MachineFunctionPass(ID) { | |||
59 | initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); | |||
60 | } | |||
61 | ||||
62 | void MachineDominatorTree::releaseMemory() { | |||
63 | CriticalEdgesToSplit.clear(); | |||
64 | DT.reset(nullptr); | |||
65 | } | |||
66 | ||||
67 | void MachineDominatorTree::verifyAnalysis() const { | |||
68 | if (DT && VerifyMachineDomInfo) | |||
| ||||
69 | verifyDomTree(); | |||
70 | } | |||
71 | ||||
72 | void MachineDominatorTree::print(raw_ostream &OS, const Module*) const { | |||
73 | if (DT) | |||
74 | DT->print(OS); | |||
75 | } | |||
76 | ||||
77 | void MachineDominatorTree::applySplitCriticalEdges() const { | |||
78 | // Bail out early if there is nothing to do. | |||
79 | if (CriticalEdgesToSplit.empty()) | |||
80 | return; | |||
81 | ||||
82 | // For each element in CriticalEdgesToSplit, remember whether or not element | |||
83 | // is the new immediate domminator of its successor. The mapping is done by | |||
84 | // index, i.e., the information for the ith element of CriticalEdgesToSplit is | |||
85 | // the ith element of IsNewIDom. | |||
86 | SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true); | |||
87 | size_t Idx = 0; | |||
88 | ||||
89 | // Collect all the dominance properties info, before invalidating | |||
90 | // the underlying DT. | |||
91 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { | |||
92 | // Update dominator information. | |||
93 | MachineBasicBlock *Succ = Edge.ToBB; | |||
94 | MachineDomTreeNode *SuccDTNode = DT->getNode(Succ); | |||
95 | ||||
96 | for (MachineBasicBlock *PredBB : Succ->predecessors()) { | |||
97 | if (PredBB == Edge.NewBB) | |||
98 | continue; | |||
99 | // If we are in this situation: | |||
100 | // FromBB1 FromBB2 | |||
101 | // + + | |||
102 | // + + + + | |||
103 | // + + + + | |||
104 | // ... Split1 Split2 ... | |||
105 | // + + | |||
106 | // + + | |||
107 | // + | |||
108 | // Succ | |||
109 | // Instead of checking the domiance property with Split2, we check it with | |||
110 | // FromBB2 since Split2 is still unknown of the underlying DT structure. | |||
111 | if (NewBBs.count(PredBB)) { | |||
112 | assert(PredBB->pred_size() == 1 && "A basic block resulting from a "(static_cast <bool> (PredBB->pred_size() == 1 && "A basic block resulting from a " "critical edge split has more " "than one predecessor!") ? void (0) : __assert_fail ("PredBB->pred_size() == 1 && \"A basic block resulting from a \" \"critical edge split has more \" \"than one predecessor!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/MachineDominators.cpp" , 114, __extension__ __PRETTY_FUNCTION__)) | |||
113 | "critical edge split has more "(static_cast <bool> (PredBB->pred_size() == 1 && "A basic block resulting from a " "critical edge split has more " "than one predecessor!") ? void (0) : __assert_fail ("PredBB->pred_size() == 1 && \"A basic block resulting from a \" \"critical edge split has more \" \"than one predecessor!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/MachineDominators.cpp" , 114, __extension__ __PRETTY_FUNCTION__)) | |||
114 | "than one predecessor!")(static_cast <bool> (PredBB->pred_size() == 1 && "A basic block resulting from a " "critical edge split has more " "than one predecessor!") ? void (0) : __assert_fail ("PredBB->pred_size() == 1 && \"A basic block resulting from a \" \"critical edge split has more \" \"than one predecessor!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/MachineDominators.cpp" , 114, __extension__ __PRETTY_FUNCTION__)); | |||
115 | PredBB = *PredBB->pred_begin(); | |||
116 | } | |||
117 | if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) { | |||
118 | IsNewIDom[Idx] = false; | |||
119 | break; | |||
120 | } | |||
121 | } | |||
122 | ++Idx; | |||
123 | } | |||
124 | ||||
125 | // Now, update DT with the collected dominance properties info. | |||
126 | Idx = 0; | |||
127 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { | |||
128 | // We know FromBB dominates NewBB. | |||
129 | MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); | |||
130 | ||||
131 | // If all the other predecessors of "Succ" are dominated by "Succ" itself | |||
132 | // then the new block is the new immediate dominator of "Succ". Otherwise, | |||
133 | // the new block doesn't dominate anything. | |||
134 | if (IsNewIDom[Idx]) | |||
135 | DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode); | |||
136 | ++Idx; | |||
137 | } | |||
138 | NewBBs.clear(); | |||
139 | CriticalEdgesToSplit.clear(); | |||
140 | } | |||
| ||||
141 | ||||
142 | void MachineDominatorTree::verifyDomTree() const { | |||
143 | if (!DT) | |||
144 | return; | |||
145 | MachineFunction &F = *getRoot()->getParent(); | |||
146 | ||||
147 | DomTreeBase<MachineBasicBlock> OtherDT; | |||
148 | OtherDT.recalculate(F); | |||
149 | if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() || | |||
150 | DT->compare(OtherDT)) { | |||
151 | errs() << "MachineDominatorTree for function " << F.getName() | |||
152 | << " is not up to date!\nComputed:\n"; | |||
153 | DT->print(errs()); | |||
154 | errs() << "\nActual:\n"; | |||
155 | OtherDT.print(errs()); | |||
156 | abort(); | |||
157 | } | |||
158 | } |
1 | //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file defines classes mirroring those in llvm/Analysis/Dominators.h, |
11 | // but for target-specific code rather than target-independent IR. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H |
16 | #define LLVM_CODEGEN_MACHINEDOMINATORS_H |
17 | |
18 | #include "llvm/ADT/SmallSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/CodeGen/MachineBasicBlock.h" |
21 | #include "llvm/CodeGen/MachineFunctionPass.h" |
22 | #include "llvm/CodeGen/MachineInstr.h" |
23 | #include "llvm/Support/GenericDomTree.h" |
24 | #include "llvm/Support/GenericDomTreeConstruction.h" |
25 | #include <cassert> |
26 | #include <memory> |
27 | #include <vector> |
28 | |
29 | namespace llvm { |
30 | |
31 | template <> |
32 | inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( |
33 | MachineBasicBlock *MBB) { |
34 | this->Roots.push_back(MBB); |
35 | } |
36 | |
37 | extern template class DomTreeNodeBase<MachineBasicBlock>; |
38 | extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree |
39 | extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree |
40 | |
41 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
42 | |
43 | //===------------------------------------- |
44 | /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to |
45 | /// compute a normal dominator tree. |
46 | /// |
47 | class MachineDominatorTree : public MachineFunctionPass { |
48 | /// \brief Helper structure used to hold all the basic blocks |
49 | /// involved in the split of a critical edge. |
50 | struct CriticalEdge { |
51 | MachineBasicBlock *FromBB; |
52 | MachineBasicBlock *ToBB; |
53 | MachineBasicBlock *NewBB; |
54 | }; |
55 | |
56 | /// \brief Pile up all the critical edges to be split. |
57 | /// The splitting of a critical edge is local and thus, it is possible |
58 | /// to apply several of those changes at the same time. |
59 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; |
60 | |
61 | /// \brief Remember all the basic blocks that are inserted during |
62 | /// edge splitting. |
63 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB |
64 | /// field of all the elements of CriticalEdgesToSplit. |
65 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs |
66 | /// such as BB == elt.NewBB. |
67 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; |
68 | |
69 | /// The DominatorTreeBase that is used to compute a normal dominator tree |
70 | std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT; |
71 | |
72 | /// \brief Apply all the recorded critical edges to the DT. |
73 | /// This updates the underlying DT information in a way that uses |
74 | /// the fast query path of DT as much as possible. |
75 | /// |
76 | /// \post CriticalEdgesToSplit.empty(). |
77 | void applySplitCriticalEdges() const; |
78 | |
79 | public: |
80 | static char ID; // Pass ID, replacement for typeid |
81 | |
82 | MachineDominatorTree(); |
83 | |
84 | DomTreeBase<MachineBasicBlock> &getBase() { |
85 | if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>()); |
86 | applySplitCriticalEdges(); |
87 | return *DT; |
88 | } |
89 | |
90 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
91 | |
92 | /// getRoots - Return the root blocks of the current CFG. This may include |
93 | /// multiple blocks if we are computing post dominators. For forward |
94 | /// dominators, this will always be a single block (the entry node). |
95 | /// |
96 | inline const SmallVectorImpl<MachineBasicBlock*> &getRoots() const { |
97 | applySplitCriticalEdges(); |
98 | return DT->getRoots(); |
99 | } |
100 | |
101 | inline MachineBasicBlock *getRoot() const { |
102 | applySplitCriticalEdges(); |
103 | return DT->getRoot(); |
104 | } |
105 | |
106 | inline MachineDomTreeNode *getRootNode() const { |
107 | applySplitCriticalEdges(); |
108 | return DT->getRootNode(); |
109 | } |
110 | |
111 | bool runOnMachineFunction(MachineFunction &F) override; |
112 | |
113 | inline bool dominates(const MachineDomTreeNode* A, |
114 | const MachineDomTreeNode* B) const { |
115 | applySplitCriticalEdges(); |
116 | return DT->dominates(A, B); |
117 | } |
118 | |
119 | inline bool dominates(const MachineBasicBlock* A, |
120 | const MachineBasicBlock* B) const { |
121 | applySplitCriticalEdges(); |
122 | return DT->dominates(A, B); |
123 | } |
124 | |
125 | // dominates - Return true if A dominates B. This performs the |
126 | // special checks necessary if A and B are in the same basic block. |
127 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
128 | applySplitCriticalEdges(); |
129 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
130 | if (BBA != BBB) return DT->dominates(BBA, BBB); |
131 | |
132 | // Loop through the basic block until we find A or B. |
133 | MachineBasicBlock::const_iterator I = BBA->begin(); |
134 | for (; &*I != A && &*I != B; ++I) |
135 | /*empty*/ ; |
136 | |
137 | //if(!DT.IsPostDominators) { |
138 | // A dominates B if it is found first in the basic block. |
139 | return &*I == A; |
140 | //} else { |
141 | // // A post-dominates B if B is found first in the basic block. |
142 | // return &*I == B; |
143 | //} |
144 | } |
145 | |
146 | inline bool properlyDominates(const MachineDomTreeNode* A, |
147 | const MachineDomTreeNode* B) const { |
148 | applySplitCriticalEdges(); |
149 | return DT->properlyDominates(A, B); |
150 | } |
151 | |
152 | inline bool properlyDominates(const MachineBasicBlock* A, |
153 | const MachineBasicBlock* B) const { |
154 | applySplitCriticalEdges(); |
155 | return DT->properlyDominates(A, B); |
156 | } |
157 | |
158 | /// findNearestCommonDominator - Find nearest common dominator basic block |
159 | /// for basic block A and B. If there is no such block then return NULL. |
160 | inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, |
161 | MachineBasicBlock *B) { |
162 | applySplitCriticalEdges(); |
163 | return DT->findNearestCommonDominator(A, B); |
164 | } |
165 | |
166 | inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
167 | applySplitCriticalEdges(); |
168 | return DT->getNode(BB); |
169 | } |
170 | |
171 | /// getNode - return the (Post)DominatorTree node for the specified basic |
172 | /// block. This is the same as using operator[] on this class. |
173 | /// |
174 | inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { |
175 | applySplitCriticalEdges(); |
176 | return DT->getNode(BB); |
177 | } |
178 | |
179 | /// addNewBlock - Add a new node to the dominator tree information. This |
180 | /// creates a new node as a child of DomBB dominator node,linking it into |
181 | /// the children list of the immediate dominator. |
182 | inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, |
183 | MachineBasicBlock *DomBB) { |
184 | applySplitCriticalEdges(); |
185 | return DT->addNewBlock(BB, DomBB); |
186 | } |
187 | |
188 | /// changeImmediateDominator - This method is used to update the dominator |
189 | /// tree information when a node's immediate dominator changes. |
190 | /// |
191 | inline void changeImmediateDominator(MachineBasicBlock *N, |
192 | MachineBasicBlock* NewIDom) { |
193 | applySplitCriticalEdges(); |
194 | DT->changeImmediateDominator(N, NewIDom); |
195 | } |
196 | |
197 | inline void changeImmediateDominator(MachineDomTreeNode *N, |
198 | MachineDomTreeNode* NewIDom) { |
199 | applySplitCriticalEdges(); |
200 | DT->changeImmediateDominator(N, NewIDom); |
201 | } |
202 | |
203 | /// eraseNode - Removes a node from the dominator tree. Block must not |
204 | /// dominate any other blocks. Removes node from its immediate dominator's |
205 | /// children list. Deletes dominator node associated with basic block BB. |
206 | inline void eraseNode(MachineBasicBlock *BB) { |
207 | applySplitCriticalEdges(); |
208 | DT->eraseNode(BB); |
209 | } |
210 | |
211 | /// splitBlock - BB is split and now it has one successor. Update dominator |
212 | /// tree to reflect this change. |
213 | inline void splitBlock(MachineBasicBlock* NewBB) { |
214 | applySplitCriticalEdges(); |
215 | DT->splitBlock(NewBB); |
216 | } |
217 | |
218 | /// isReachableFromEntry - Return true if A is dominated by the entry |
219 | /// block of the function containing it. |
220 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
221 | applySplitCriticalEdges(); |
222 | return DT->isReachableFromEntry(A); |
223 | } |
224 | |
225 | void releaseMemory() override; |
226 | |
227 | void verifyAnalysis() const override; |
228 | |
229 | void print(raw_ostream &OS, const Module*) const override; |
230 | |
231 | /// \brief Record that the critical edge (FromBB, ToBB) has been |
232 | /// split with NewBB. |
233 | /// This is best to use this method instead of directly update the |
234 | /// underlying information, because this helps mitigating the |
235 | /// number of time the DT information is invalidated. |
236 | /// |
237 | /// \note Do not use this method with regular edges. |
238 | /// |
239 | /// \note To benefit from the compile time improvement incurred by this |
240 | /// method, the users of this method have to limit the queries to the DT |
241 | /// interface between two edges splitting. In other words, they have to |
242 | /// pack the splitting of critical edges as much as possible. |
243 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, |
244 | MachineBasicBlock *ToBB, |
245 | MachineBasicBlock *NewBB) { |
246 | bool Inserted = NewBBs.insert(NewBB).second; |
247 | (void)Inserted; |
248 | assert(Inserted &&(static_cast <bool> (Inserted && "A basic block inserted via edge splitting cannot appear twice" ) ? void (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineDominators.h" , 249, __extension__ __PRETTY_FUNCTION__)) |
249 | "A basic block inserted via edge splitting cannot appear twice")(static_cast <bool> (Inserted && "A basic block inserted via edge splitting cannot appear twice" ) ? void (0) : __assert_fail ("Inserted && \"A basic block inserted via edge splitting cannot appear twice\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineDominators.h" , 249, __extension__ __PRETTY_FUNCTION__)); |
250 | CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); |
251 | } |
252 | |
253 | /// \brief Verify the correctness of the domtree by re-computing it. |
254 | /// |
255 | /// This should only be used for debugging as it aborts the program if the |
256 | /// verification fails. |
257 | void verifyDomTree() const; |
258 | }; |
259 | |
260 | //===------------------------------------- |
261 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
262 | /// iterable by generic graph iterators. |
263 | /// |
264 | |
265 | template <class Node, class ChildIterator> |
266 | struct MachineDomTreeGraphTraitsBase { |
267 | using NodeRef = Node *; |
268 | using ChildIteratorType = ChildIterator; |
269 | |
270 | static NodeRef getEntryNode(NodeRef N) { return N; } |
271 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
272 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
273 | }; |
274 | |
275 | template <class T> struct GraphTraits; |
276 | |
277 | template <> |
278 | struct GraphTraits<MachineDomTreeNode *> |
279 | : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, |
280 | MachineDomTreeNode::iterator> {}; |
281 | |
282 | template <> |
283 | struct GraphTraits<const MachineDomTreeNode *> |
284 | : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, |
285 | MachineDomTreeNode::const_iterator> { |
286 | }; |
287 | |
288 | template <> struct GraphTraits<MachineDominatorTree*> |
289 | : public GraphTraits<MachineDomTreeNode *> { |
290 | static NodeRef getEntryNode(MachineDominatorTree *DT) { |
291 | return DT->getRootNode(); |
292 | } |
293 | }; |
294 | |
295 | } // end namespace llvm |
296 | |
297 | #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H |
1 | //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// |
2 | // |
3 | // The LLVM Compiler Infrastructure |
4 | // |
5 | // This file is distributed under the University of Illinois Open Source |
6 | // License. See LICENSE.TXT for details. |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | // |
10 | // This file implements the SmallBitVector class. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ADT_SMALLBITVECTOR_H |
15 | #define LLVM_ADT_SMALLBITVECTOR_H |
16 | |
17 | #include "llvm/ADT/BitVector.h" |
18 | #include "llvm/ADT/iterator_range.h" |
19 | #include "llvm/Support/MathExtras.h" |
20 | #include <algorithm> |
21 | #include <cassert> |
22 | #include <climits> |
23 | #include <cstddef> |
24 | #include <cstdint> |
25 | #include <limits> |
26 | #include <utility> |
27 | |
28 | namespace llvm { |
29 | |
30 | /// This is a 'bitvector' (really, a variable-sized bit array), optimized for |
31 | /// the case when the array is small. It contains one pointer-sized field, which |
32 | /// is directly used as a plain collection of bits when possible, or as a |
33 | /// pointer to a larger heap-allocated array when necessary. This allows normal |
34 | /// "small" cases to be fast without losing generality for large inputs. |
35 | class SmallBitVector { |
36 | // TODO: In "large" mode, a pointer to a BitVector is used, leading to an |
37 | // unnecessary level of indirection. It would be more efficient to use a |
38 | // pointer to memory containing size, allocation size, and the array of bits. |
39 | uintptr_t X = 1; |
40 | |
41 | enum { |
42 | // The number of bits in this class. |
43 | NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8, |
44 | |
45 | // One bit is used to discriminate between small and large mode. The |
46 | // remaining bits are used for the small-mode representation. |
47 | SmallNumRawBits = NumBaseBits - 1, |
48 | |
49 | // A few more bits are used to store the size of the bit set in small mode. |
50 | // Theoretically this is a ceil-log2. These bits are encoded in the most |
51 | // significant bits of the raw bits. |
52 | SmallNumSizeBits = (NumBaseBits == 32 ? 5 : |
53 | NumBaseBits == 64 ? 6 : |
54 | SmallNumRawBits), |
55 | |
56 | // The remaining bits are used to store the actual set in small mode. |
57 | SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits |
58 | }; |
59 | |
60 | static_assert(NumBaseBits == 64 || NumBaseBits == 32, |
61 | "Unsupported word size"); |
62 | |
63 | public: |
64 | using size_type = unsigned; |
65 | |
66 | // Encapsulation of a single bit. |
67 | class reference { |
68 | SmallBitVector &TheVector; |
69 | unsigned BitPos; |
70 | |
71 | public: |
72 | reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} |
73 | |
74 | reference(const reference&) = default; |
75 | |
76 | reference& operator=(reference t) { |
77 | *this = bool(t); |
78 | return *this; |
79 | } |
80 | |
81 | reference& operator=(bool t) { |
82 | if (t) |
83 | TheVector.set(BitPos); |
84 | else |
85 | TheVector.reset(BitPos); |
86 | return *this; |
87 | } |
88 | |
89 | operator bool() const { |
90 | return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); |
91 | } |
92 | }; |
93 | |
94 | private: |
95 | bool isSmall() const { |
96 | return X & uintptr_t(1); |
97 | } |
98 | |
99 | BitVector *getPointer() const { |
100 | assert(!isSmall())(static_cast <bool> (!isSmall()) ? void (0) : __assert_fail ("!isSmall()", "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 100, __extension__ __PRETTY_FUNCTION__)); |
101 | return reinterpret_cast<BitVector *>(X); |
102 | } |
103 | |
104 | void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { |
105 | X = 1; |
106 | setSmallSize(NewSize); |
107 | setSmallBits(NewSmallBits); |
108 | } |
109 | |
110 | void switchToLarge(BitVector *BV) { |
111 | X = reinterpret_cast<uintptr_t>(BV); |
112 | assert(!isSmall() && "Tried to use an unaligned pointer")(static_cast <bool> (!isSmall() && "Tried to use an unaligned pointer" ) ? void (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 112, __extension__ __PRETTY_FUNCTION__)); |
113 | } |
114 | |
115 | // Return all the bits used for the "small" representation; this includes |
116 | // bits for the size as well as the element bits. |
117 | uintptr_t getSmallRawBits() const { |
118 | assert(isSmall())(static_cast <bool> (isSmall()) ? void (0) : __assert_fail ("isSmall()", "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 118, __extension__ __PRETTY_FUNCTION__)); |
119 | return X >> 1; |
120 | } |
121 | |
122 | void setSmallRawBits(uintptr_t NewRawBits) { |
123 | assert(isSmall())(static_cast <bool> (isSmall()) ? void (0) : __assert_fail ("isSmall()", "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 123, __extension__ __PRETTY_FUNCTION__)); |
124 | X = (NewRawBits << 1) | uintptr_t(1); |
125 | } |
126 | |
127 | // Return the size. |
128 | size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } |
129 | |
130 | void setSmallSize(size_t Size) { |
131 | setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); |
132 | } |
133 | |
134 | // Return the element bits. |
135 | uintptr_t getSmallBits() const { |
136 | return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); |
137 | } |
138 | |
139 | void setSmallBits(uintptr_t NewBits) { |
140 | setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | |
141 | (getSmallSize() << SmallNumDataBits)); |
142 | } |
143 | |
144 | public: |
145 | /// Creates an empty bitvector. |
146 | SmallBitVector() = default; |
147 | |
148 | /// Creates a bitvector of specified number of bits. All bits are initialized |
149 | /// to the specified value. |
150 | explicit SmallBitVector(unsigned s, bool t = false) { |
151 | if (s <= SmallNumDataBits) |
152 | switchToSmall(t ? ~uintptr_t(0) : 0, s); |
153 | else |
154 | switchToLarge(new BitVector(s, t)); |
155 | } |
156 | |
157 | /// SmallBitVector copy ctor. |
158 | SmallBitVector(const SmallBitVector &RHS) { |
159 | if (RHS.isSmall()) |
160 | X = RHS.X; |
161 | else |
162 | switchToLarge(new BitVector(*RHS.getPointer())); |
163 | } |
164 | |
165 | SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { |
166 | RHS.X = 1; |
167 | } |
168 | |
169 | ~SmallBitVector() { |
170 | if (!isSmall()) |
171 | delete getPointer(); |
172 | } |
173 | |
174 | using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; |
175 | using set_iterator = const_set_bits_iterator; |
176 | |
177 | const_set_bits_iterator set_bits_begin() const { |
178 | return const_set_bits_iterator(*this); |
179 | } |
180 | |
181 | const_set_bits_iterator set_bits_end() const { |
182 | return const_set_bits_iterator(*this, -1); |
183 | } |
184 | |
185 | iterator_range<const_set_bits_iterator> set_bits() const { |
186 | return make_range(set_bits_begin(), set_bits_end()); |
187 | } |
188 | |
189 | /// Tests whether there are no bits in this bitvector. |
190 | bool empty() const { |
191 | return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); |
192 | } |
193 | |
194 | /// Returns the number of bits in this bitvector. |
195 | size_t size() const { |
196 | return isSmall() ? getSmallSize() : getPointer()->size(); |
197 | } |
198 | |
199 | /// Returns the number of bits which are set. |
200 | size_type count() const { |
201 | if (isSmall()) { |
202 | uintptr_t Bits = getSmallBits(); |
203 | return countPopulation(Bits); |
204 | } |
205 | return getPointer()->count(); |
206 | } |
207 | |
208 | /// Returns true if any bit is set. |
209 | bool any() const { |
210 | if (isSmall()) |
211 | return getSmallBits() != 0; |
212 | return getPointer()->any(); |
213 | } |
214 | |
215 | /// Returns true if all bits are set. |
216 | bool all() const { |
217 | if (isSmall()) |
218 | return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; |
219 | return getPointer()->all(); |
220 | } |
221 | |
222 | /// Returns true if none of the bits are set. |
223 | bool none() const { |
224 | if (isSmall()) |
225 | return getSmallBits() == 0; |
226 | return getPointer()->none(); |
227 | } |
228 | |
229 | /// Returns the index of the first set bit, -1 if none of the bits are set. |
230 | int find_first() const { |
231 | if (isSmall()) { |
232 | uintptr_t Bits = getSmallBits(); |
233 | if (Bits == 0) |
234 | return -1; |
235 | return countTrailingZeros(Bits); |
236 | } |
237 | return getPointer()->find_first(); |
238 | } |
239 | |
240 | int find_last() const { |
241 | if (isSmall()) { |
242 | uintptr_t Bits = getSmallBits(); |
243 | if (Bits == 0) |
244 | return -1; |
245 | return NumBaseBits - countLeadingZeros(Bits); |
246 | } |
247 | return getPointer()->find_last(); |
248 | } |
249 | |
250 | /// Returns the index of the first unset bit, -1 if all of the bits are set. |
251 | int find_first_unset() const { |
252 | if (isSmall()) { |
253 | if (count() == getSmallSize()) |
254 | return -1; |
255 | |
256 | uintptr_t Bits = getSmallBits(); |
257 | return countTrailingOnes(Bits); |
258 | } |
259 | return getPointer()->find_first_unset(); |
260 | } |
261 | |
262 | int find_last_unset() const { |
263 | if (isSmall()) { |
264 | if (count() == getSmallSize()) |
265 | return -1; |
266 | |
267 | uintptr_t Bits = getSmallBits(); |
268 | return NumBaseBits - countLeadingOnes(Bits); |
269 | } |
270 | return getPointer()->find_last_unset(); |
271 | } |
272 | |
273 | /// Returns the index of the next set bit following the "Prev" bit. |
274 | /// Returns -1 if the next set bit is not found. |
275 | int find_next(unsigned Prev) const { |
276 | if (isSmall()) { |
277 | uintptr_t Bits = getSmallBits(); |
278 | // Mask off previous bits. |
279 | Bits &= ~uintptr_t(0) << (Prev + 1); |
280 | if (Bits == 0 || Prev + 1 >= getSmallSize()) |
281 | return -1; |
282 | return countTrailingZeros(Bits); |
283 | } |
284 | return getPointer()->find_next(Prev); |
285 | } |
286 | |
287 | /// Returns the index of the next unset bit following the "Prev" bit. |
288 | /// Returns -1 if the next unset bit is not found. |
289 | int find_next_unset(unsigned Prev) const { |
290 | if (isSmall()) { |
291 | ++Prev; |
292 | uintptr_t Bits = getSmallBits(); |
293 | // Mask in previous bits. |
294 | uintptr_t Mask = (1 << Prev) - 1; |
295 | Bits |= Mask; |
296 | |
297 | if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) |
298 | return -1; |
299 | return countTrailingOnes(Bits); |
300 | } |
301 | return getPointer()->find_next_unset(Prev); |
302 | } |
303 | |
304 | /// find_prev - Returns the index of the first set bit that precedes the |
305 | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. |
306 | int find_prev(unsigned PriorTo) const { |
307 | if (isSmall()) { |
308 | if (PriorTo == 0) |
309 | return -1; |
310 | |
311 | --PriorTo; |
312 | uintptr_t Bits = getSmallBits(); |
313 | Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1); |
314 | if (Bits == 0) |
315 | return -1; |
316 | |
317 | return NumBaseBits - countLeadingZeros(Bits) - 1; |
318 | } |
319 | return getPointer()->find_prev(PriorTo); |
320 | } |
321 | |
322 | /// Clear all bits. |
323 | void clear() { |
324 | if (!isSmall()) |
325 | delete getPointer(); |
326 | switchToSmall(0, 0); |
327 | } |
328 | |
329 | /// Grow or shrink the bitvector. |
330 | void resize(unsigned N, bool t = false) { |
331 | if (!isSmall()) { |
332 | getPointer()->resize(N, t); |
333 | } else if (SmallNumDataBits >= N) { |
334 | uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; |
335 | setSmallSize(N); |
336 | setSmallBits(NewBits | getSmallBits()); |
337 | } else { |
338 | BitVector *BV = new BitVector(N, t); |
339 | uintptr_t OldBits = getSmallBits(); |
340 | for (size_t i = 0, e = getSmallSize(); i != e; ++i) |
341 | (*BV)[i] = (OldBits >> i) & 1; |
342 | switchToLarge(BV); |
343 | } |
344 | } |
345 | |
346 | void reserve(unsigned N) { |
347 | if (isSmall()) { |
348 | if (N > SmallNumDataBits) { |
349 | uintptr_t OldBits = getSmallRawBits(); |
350 | size_t SmallSize = getSmallSize(); |
351 | BitVector *BV = new BitVector(SmallSize); |
352 | for (size_t i = 0; i < SmallSize; ++i) |
353 | if ((OldBits >> i) & 1) |
354 | BV->set(i); |
355 | BV->reserve(N); |
356 | switchToLarge(BV); |
357 | } |
358 | } else { |
359 | getPointer()->reserve(N); |
360 | } |
361 | } |
362 | |
363 | // Set, reset, flip |
364 | SmallBitVector &set() { |
365 | if (isSmall()) |
366 | setSmallBits(~uintptr_t(0)); |
367 | else |
368 | getPointer()->set(); |
369 | return *this; |
370 | } |
371 | |
372 | SmallBitVector &set(unsigned Idx) { |
373 | if (isSmall()) { |
374 | assert(Idx <= static_cast<unsigned>((static_cast <bool> (Idx <= static_cast<unsigned> ( std::numeric_limits<uintptr_t>::digits) && "undefined behavior" ) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 376, __extension__ __PRETTY_FUNCTION__)) |
375 | std::numeric_limits<uintptr_t>::digits) &&(static_cast <bool> (Idx <= static_cast<unsigned> ( std::numeric_limits<uintptr_t>::digits) && "undefined behavior" ) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 376, __extension__ __PRETTY_FUNCTION__)) |
376 | "undefined behavior")(static_cast <bool> (Idx <= static_cast<unsigned> ( std::numeric_limits<uintptr_t>::digits) && "undefined behavior" ) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 376, __extension__ __PRETTY_FUNCTION__)); |
377 | setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); |
378 | } |
379 | else |
380 | getPointer()->set(Idx); |
381 | return *this; |
382 | } |
383 | |
384 | /// Efficiently set a range of bits in [I, E) |
385 | SmallBitVector &set(unsigned I, unsigned E) { |
386 | assert(I <= E && "Attempted to set backwards range!")(static_cast <bool> (I <= E && "Attempted to set backwards range!" ) ? void (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 386, __extension__ __PRETTY_FUNCTION__)); |
387 | assert(E <= size() && "Attempted to set out-of-bounds range!")(static_cast <bool> (E <= size() && "Attempted to set out-of-bounds range!" ) ? void (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 387, __extension__ __PRETTY_FUNCTION__)); |
388 | if (I == E) return *this; |
389 | if (isSmall()) { |
390 | uintptr_t EMask = ((uintptr_t)1) << E; |
391 | uintptr_t IMask = ((uintptr_t)1) << I; |
392 | uintptr_t Mask = EMask - IMask; |
393 | setSmallBits(getSmallBits() | Mask); |
394 | } else |
395 | getPointer()->set(I, E); |
396 | return *this; |
397 | } |
398 | |
399 | SmallBitVector &reset() { |
400 | if (isSmall()) |
401 | setSmallBits(0); |
402 | else |
403 | getPointer()->reset(); |
404 | return *this; |
405 | } |
406 | |
407 | SmallBitVector &reset(unsigned Idx) { |
408 | if (isSmall()) |
409 | setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); |
410 | else |
411 | getPointer()->reset(Idx); |
412 | return *this; |
413 | } |
414 | |
415 | /// Efficiently reset a range of bits in [I, E) |
416 | SmallBitVector &reset(unsigned I, unsigned E) { |
417 | assert(I <= E && "Attempted to reset backwards range!")(static_cast <bool> (I <= E && "Attempted to reset backwards range!" ) ? void (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 417, __extension__ __PRETTY_FUNCTION__)); |
418 | assert(E <= size() && "Attempted to reset out-of-bounds range!")(static_cast <bool> (E <= size() && "Attempted to reset out-of-bounds range!" ) ? void (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 418, __extension__ __PRETTY_FUNCTION__)); |
419 | if (I == E) return *this; |
420 | if (isSmall()) { |
421 | uintptr_t EMask = ((uintptr_t)1) << E; |
422 | uintptr_t IMask = ((uintptr_t)1) << I; |
423 | uintptr_t Mask = EMask - IMask; |
424 | setSmallBits(getSmallBits() & ~Mask); |
425 | } else |
426 | getPointer()->reset(I, E); |
427 | return *this; |
428 | } |
429 | |
430 | SmallBitVector &flip() { |
431 | if (isSmall()) |
432 | setSmallBits(~getSmallBits()); |
433 | else |
434 | getPointer()->flip(); |
435 | return *this; |
436 | } |
437 | |
438 | SmallBitVector &flip(unsigned Idx) { |
439 | if (isSmall()) |
440 | setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); |
441 | else |
442 | getPointer()->flip(Idx); |
443 | return *this; |
444 | } |
445 | |
446 | // No argument flip. |
447 | SmallBitVector operator~() const { |
448 | return SmallBitVector(*this).flip(); |
449 | } |
450 | |
451 | // Indexing. |
452 | reference operator[](unsigned Idx) { |
453 | assert(Idx < size() && "Out-of-bounds Bit access.")(static_cast <bool> (Idx < size() && "Out-of-bounds Bit access." ) ? void (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 453, __extension__ __PRETTY_FUNCTION__)); |
454 | return reference(*this, Idx); |
455 | } |
456 | |
457 | bool operator[](unsigned Idx) const { |
458 | assert(Idx < size() && "Out-of-bounds Bit access.")(static_cast <bool> (Idx < size() && "Out-of-bounds Bit access." ) ? void (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 458, __extension__ __PRETTY_FUNCTION__)); |
459 | if (isSmall()) |
460 | return ((getSmallBits() >> Idx) & 1) != 0; |
461 | return getPointer()->operator[](Idx); |
462 | } |
463 | |
464 | bool test(unsigned Idx) const { |
465 | return (*this)[Idx]; |
466 | } |
467 | |
468 | /// Test if any common bits are set. |
469 | bool anyCommon(const SmallBitVector &RHS) const { |
470 | if (isSmall() && RHS.isSmall()) |
471 | return (getSmallBits() & RHS.getSmallBits()) != 0; |
472 | if (!isSmall() && !RHS.isSmall()) |
473 | return getPointer()->anyCommon(*RHS.getPointer()); |
474 | |
475 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
476 | if (test(i) && RHS.test(i)) |
477 | return true; |
478 | return false; |
479 | } |
480 | |
481 | // Comparison operators. |
482 | bool operator==(const SmallBitVector &RHS) const { |
483 | if (size() != RHS.size()) |
484 | return false; |
485 | if (isSmall()) |
486 | return getSmallBits() == RHS.getSmallBits(); |
487 | else |
488 | return *getPointer() == *RHS.getPointer(); |
489 | } |
490 | |
491 | bool operator!=(const SmallBitVector &RHS) const { |
492 | return !(*this == RHS); |
493 | } |
494 | |
495 | // Intersection, union, disjoint union. |
496 | SmallBitVector &operator&=(const SmallBitVector &RHS) { |
497 | resize(std::max(size(), RHS.size())); |
498 | if (isSmall()) |
499 | setSmallBits(getSmallBits() & RHS.getSmallBits()); |
500 | else if (!RHS.isSmall()) |
501 | getPointer()->operator&=(*RHS.getPointer()); |
502 | else { |
503 | SmallBitVector Copy = RHS; |
504 | Copy.resize(size()); |
505 | getPointer()->operator&=(*Copy.getPointer()); |
506 | } |
507 | return *this; |
508 | } |
509 | |
510 | /// Reset bits that are set in RHS. Same as *this &= ~RHS. |
511 | SmallBitVector &reset(const SmallBitVector &RHS) { |
512 | if (isSmall() && RHS.isSmall()) |
513 | setSmallBits(getSmallBits() & ~RHS.getSmallBits()); |
514 | else if (!isSmall() && !RHS.isSmall()) |
515 | getPointer()->reset(*RHS.getPointer()); |
516 | else |
517 | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
518 | if (RHS.test(i)) |
519 | reset(i); |
520 | |
521 | return *this; |
522 | } |
523 | |
524 | /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). |
525 | bool test(const SmallBitVector &RHS) const { |
526 | if (isSmall() && RHS.isSmall()) |
527 | return (getSmallBits() & ~RHS.getSmallBits()) != 0; |
528 | if (!isSmall() && !RHS.isSmall()) |
529 | return getPointer()->test(*RHS.getPointer()); |
530 | |
531 | unsigned i, e; |
532 | for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
533 | if (test(i) && !RHS.test(i)) |
534 | return true; |
535 | |
536 | for (e = size(); i != e; ++i) |
537 | if (test(i)) |
538 | return true; |
539 | |
540 | return false; |
541 | } |
542 | |
543 | SmallBitVector &operator|=(const SmallBitVector &RHS) { |
544 | resize(std::max(size(), RHS.size())); |
545 | if (isSmall()) |
546 | setSmallBits(getSmallBits() | RHS.getSmallBits()); |
547 | else if (!RHS.isSmall()) |
548 | getPointer()->operator|=(*RHS.getPointer()); |
549 | else { |
550 | SmallBitVector Copy = RHS; |
551 | Copy.resize(size()); |
552 | getPointer()->operator|=(*Copy.getPointer()); |
553 | } |
554 | return *this; |
555 | } |
556 | |
557 | SmallBitVector &operator^=(const SmallBitVector &RHS) { |
558 | resize(std::max(size(), RHS.size())); |
559 | if (isSmall()) |
560 | setSmallBits(getSmallBits() ^ RHS.getSmallBits()); |
561 | else if (!RHS.isSmall()) |
562 | getPointer()->operator^=(*RHS.getPointer()); |
563 | else { |
564 | SmallBitVector Copy = RHS; |
565 | Copy.resize(size()); |
566 | getPointer()->operator^=(*Copy.getPointer()); |
567 | } |
568 | return *this; |
569 | } |
570 | |
571 | SmallBitVector &operator<<=(unsigned N) { |
572 | if (isSmall()) |
573 | setSmallBits(getSmallBits() << N); |
574 | else |
575 | getPointer()->operator<<=(N); |
576 | return *this; |
577 | } |
578 | |
579 | SmallBitVector &operator>>=(unsigned N) { |
580 | if (isSmall()) |
581 | setSmallBits(getSmallBits() >> N); |
582 | else |
583 | getPointer()->operator>>=(N); |
584 | return *this; |
585 | } |
586 | |
587 | // Assignment operator. |
588 | const SmallBitVector &operator=(const SmallBitVector &RHS) { |
589 | if (isSmall()) { |
590 | if (RHS.isSmall()) |
591 | X = RHS.X; |
592 | else |
593 | switchToLarge(new BitVector(*RHS.getPointer())); |
594 | } else { |
595 | if (!RHS.isSmall()) |
596 | *getPointer() = *RHS.getPointer(); |
597 | else { |
598 | delete getPointer(); |
599 | X = RHS.X; |
600 | } |
601 | } |
602 | return *this; |
603 | } |
604 | |
605 | const SmallBitVector &operator=(SmallBitVector &&RHS) { |
606 | if (this != &RHS) { |
607 | clear(); |
608 | swap(RHS); |
609 | } |
610 | return *this; |
611 | } |
612 | |
613 | void swap(SmallBitVector &RHS) { |
614 | std::swap(X, RHS.X); |
615 | } |
616 | |
617 | /// Add '1' bits from Mask to this vector. Don't resize. |
618 | /// This computes "*this |= Mask". |
619 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
620 | if (isSmall()) |
621 | applyMask<true, false>(Mask, MaskWords); |
622 | else |
623 | getPointer()->setBitsInMask(Mask, MaskWords); |
624 | } |
625 | |
626 | /// Clear any bits in this vector that are set in Mask. Don't resize. |
627 | /// This computes "*this &= ~Mask". |
628 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
629 | if (isSmall()) |
630 | applyMask<false, false>(Mask, MaskWords); |
631 | else |
632 | getPointer()->clearBitsInMask(Mask, MaskWords); |
633 | } |
634 | |
635 | /// Add a bit to this vector for every '0' bit in Mask. Don't resize. |
636 | /// This computes "*this |= ~Mask". |
637 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
638 | if (isSmall()) |
639 | applyMask<true, true>(Mask, MaskWords); |
640 | else |
641 | getPointer()->setBitsNotInMask(Mask, MaskWords); |
642 | } |
643 | |
644 | /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. |
645 | /// This computes "*this &= Mask". |
646 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
647 | if (isSmall()) |
648 | applyMask<false, true>(Mask, MaskWords); |
649 | else |
650 | getPointer()->clearBitsNotInMask(Mask, MaskWords); |
651 | } |
652 | |
653 | private: |
654 | template <bool AddBits, bool InvertMask> |
655 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |
656 | assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")(static_cast <bool> (MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!") ? void (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\"" , "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/ADT/SmallBitVector.h" , 656, __extension__ __PRETTY_FUNCTION__)); |
657 | uintptr_t M = Mask[0]; |
658 | if (NumBaseBits == 64) |
659 | M |= uint64_t(Mask[1]) << 32; |
660 | if (InvertMask) |
661 | M = ~M; |
662 | if (AddBits) |
663 | setSmallBits(getSmallBits() | M); |
664 | else |
665 | setSmallBits(getSmallBits() & ~M); |
666 | } |
667 | }; |
668 | |
669 | inline SmallBitVector |
670 | operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
671 | SmallBitVector Result(LHS); |
672 | Result &= RHS; |
673 | return Result; |
674 | } |
675 | |
676 | inline SmallBitVector |
677 | operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
678 | SmallBitVector Result(LHS); |
679 | Result |= RHS; |
680 | return Result; |
681 | } |
682 | |
683 | inline SmallBitVector |
684 | operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
685 | SmallBitVector Result(LHS); |
686 | Result ^= RHS; |
687 | return Result; |
688 | } |
689 | |
690 | } // end namespace llvm |
691 | |
692 | namespace std { |
693 | |
694 | /// Implement std::swap in terms of BitVector swap. |
695 | inline void |
696 | swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { |
697 | LHS.swap(RHS); |
698 | } |
699 | |
700 | } // end namespace std |
701 | |
702 | #endif // LLVM_ADT_SMALLBITVECTOR_H |