/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/PowerPC/PPCBoolRetToInt.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- PPCBoolRetToInt.cpp ------------------------------------------------===// |
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 converting i1 values to i32/i64 if they could be more |
11 | | // profitably allocated as GPRs rather than CRs. This pass will become totally |
12 | | // unnecessary if Register Bank Allocation and Global Instruction Selection ever |
13 | | // go upstream. |
14 | | // |
15 | | // Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the |
16 | | // transitive closure of their uses includes only PHINodes, CallInsts, and |
17 | | // ReturnInsts. The rational is that arguments are generally passed and returned |
18 | | // in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will |
19 | | // actually save casts at the Machine Instruction level. |
20 | | // |
21 | | // It might be useful to expand this pass to add bit-wise operations to the list |
22 | | // of safe transitive closure types. Also, we miss some opportunities when LLVM |
23 | | // represents logical AND and OR operations with control flow rather than data |
24 | | // flow. For example by lowering the expression: return (A && B && C) |
25 | | // |
26 | | // as: return A ? true : B && C. |
27 | | // |
28 | | // There's code in SimplifyCFG that code be used to turn control flow in data |
29 | | // flow using SelectInsts. Selects are slow on some architectures (P7/P8), so |
30 | | // this probably isn't good in general, but for the special case of i1, the |
31 | | // Selects could be further lowered to bit operations that are fast everywhere. |
32 | | // |
33 | | //===----------------------------------------------------------------------===// |
34 | | |
35 | | #include "PPC.h" |
36 | | #include "PPCTargetMachine.h" |
37 | | #include "llvm/ADT/DenseMap.h" |
38 | | #include "llvm/ADT/STLExtras.h" |
39 | | #include "llvm/ADT/SmallPtrSet.h" |
40 | | #include "llvm/ADT/SmallVector.h" |
41 | | #include "llvm/ADT/Statistic.h" |
42 | | #include "llvm/IR/Argument.h" |
43 | | #include "llvm/IR/Constants.h" |
44 | | #include "llvm/IR/Dominators.h" |
45 | | #include "llvm/IR/Function.h" |
46 | | #include "llvm/IR/Instruction.h" |
47 | | #include "llvm/IR/Instructions.h" |
48 | | #include "llvm/IR/IntrinsicInst.h" |
49 | | #include "llvm/IR/OperandTraits.h" |
50 | | #include "llvm/IR/Type.h" |
51 | | #include "llvm/IR/Use.h" |
52 | | #include "llvm/IR/User.h" |
53 | | #include "llvm/IR/Value.h" |
54 | | #include "llvm/Pass.h" |
55 | | #include "llvm/CodeGen/TargetPassConfig.h" |
56 | | #include "llvm/Support/Casting.h" |
57 | | #include <cassert> |
58 | | |
59 | | using namespace llvm; |
60 | | |
61 | | namespace { |
62 | | |
63 | | #define DEBUG_TYPE "bool-ret-to-int" |
64 | | |
65 | | STATISTIC(NumBoolRetPromotion, |
66 | | "Number of times a bool feeding a RetInst was promoted to an int"); |
67 | | STATISTIC(NumBoolCallPromotion, |
68 | | "Number of times a bool feeding a CallInst was promoted to an int"); |
69 | | STATISTIC(NumBoolToIntPromotion, |
70 | | "Total number of times a bool was promoted to an int"); |
71 | | |
72 | | class PPCBoolRetToInt : public FunctionPass { |
73 | 140 | static SmallPtrSet<Value *, 8> findAllDefs(Value *V) { |
74 | 140 | SmallPtrSet<Value *, 8> Defs; |
75 | 140 | SmallVector<Value *, 8> WorkList; |
76 | 140 | WorkList.push_back(V); |
77 | 140 | Defs.insert(V); |
78 | 533 | while (!WorkList.empty()533 ) { |
79 | 393 | Value *Curr = WorkList.back(); |
80 | 393 | WorkList.pop_back(); |
81 | 393 | auto *CurrUser = dyn_cast<User>(Curr); |
82 | 393 | // Operands of CallInst are skipped because they may not be Bool type, |
83 | 393 | // and their positions are defined by ABI. |
84 | 393 | if (CurrUser && 393 !isa<CallInst>(Curr)306 ) |
85 | 297 | for (auto &Op : CurrUser->operands()) |
86 | 285 | if (285 Defs.insert(Op).second285 ) |
87 | 253 | WorkList.push_back(Op); |
88 | 393 | } |
89 | 140 | return Defs; |
90 | 140 | } |
91 | | |
92 | | // Translate a i1 value to an equivalent i32/i64 value: |
93 | 23 | Value *translate(Value *V) { |
94 | 23 | Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext()) |
95 | 0 | : Type::getInt32Ty(V->getContext()); |
96 | 23 | |
97 | 23 | if (auto *C = dyn_cast<Constant>(V)) |
98 | 10 | return ConstantExpr::getZExt(C, IntTy); |
99 | 13 | if (auto *13 P13 = dyn_cast<PHINode>(V)) { |
100 | 10 | // Temporarily set the operands to 0. We'll fix this later in |
101 | 10 | // runOnUse. |
102 | 10 | Value *Zero = Constant::getNullValue(IntTy); |
103 | 10 | PHINode *Q = |
104 | 10 | PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P); |
105 | 29 | for (unsigned i = 0; i < P->getNumOperands()29 ; ++i19 ) |
106 | 19 | Q->addIncoming(Zero, P->getIncomingBlock(i)); |
107 | 10 | return Q; |
108 | 10 | } |
109 | 3 | |
110 | 3 | auto *A = dyn_cast<Argument>(V); |
111 | 3 | auto *I = dyn_cast<Instruction>(V); |
112 | 3 | assert((A || I) && "Unknown value type"); |
113 | 3 | |
114 | 3 | auto InstPt = |
115 | 3 | A ? &*A->getParent()->getEntryBlock().begin()2 : I->getNextNode()1 ; |
116 | 23 | return new ZExtInst(V, IntTy, "", InstPt); |
117 | 23 | } |
118 | | |
119 | | typedef SmallPtrSet<const PHINode *, 8> PHINodeSet; |
120 | | |
121 | | // A PHINode is Promotable if: |
122 | | // 1. Its type is i1 AND |
123 | | // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic |
124 | | // AND |
125 | | // 3. All of its operands are Constant or Argument or |
126 | | // CallInst or PHINode AND |
127 | | // 4. All of its PHINode uses are Promotable AND |
128 | | // 5. All of its PHINode operands are Promotable |
129 | 6.90k | static PHINodeSet getPromotablePHINodes(const Function &F) { |
130 | 6.90k | PHINodeSet Promotable; |
131 | 6.90k | // Condition 1 |
132 | 6.90k | for (auto &BB : F) |
133 | 9.88k | for (auto &I : BB) |
134 | 36.8k | if (const auto *36.8k P36.8k = dyn_cast<PHINode>(&I)) |
135 | 668 | if (668 P->getType()->isIntegerTy(1)668 ) |
136 | 16 | Promotable.insert(P); |
137 | 6.90k | |
138 | 6.90k | SmallVector<const PHINode *, 8> ToRemove; |
139 | 16 | for (const PHINode *P : Promotable) { |
140 | 16 | // Condition 2 and 3 |
141 | 19 | auto IsValidUser = [] (const Value *V) -> bool { |
142 | 19 | return isa<ReturnInst>(V) || isa<CallInst>(V)12 || isa<PHINode>(V)10 || |
143 | 5 | isa<DbgInfoIntrinsic>(V); |
144 | 19 | }; |
145 | 21 | auto IsValidOperand = [] (const Value *V) -> bool { |
146 | 21 | return isa<Constant>(V) || isa<Argument>(V)7 || isa<CallInst>(V)5 || |
147 | 5 | isa<PHINode>(V); |
148 | 21 | }; |
149 | 16 | const auto &Users = P->users(); |
150 | 16 | const auto &Operands = P->operands(); |
151 | 16 | if (!llvm::all_of(Users, IsValidUser) || |
152 | 11 | !llvm::all_of(Operands, IsValidOperand)) |
153 | 5 | ToRemove.push_back(P); |
154 | 16 | } |
155 | 6.90k | |
156 | 6.90k | // Iterate to convergence |
157 | 3 | auto IsPromotable = [&Promotable] (const Value *V) -> bool { |
158 | 3 | const auto *Phi = dyn_cast<PHINode>(V); |
159 | 1 | return !Phi || Promotable.count(Phi); |
160 | 3 | }; |
161 | 6.90k | while (!ToRemove.empty()6.90k ) { |
162 | 6 | for (auto &User : ToRemove) |
163 | 6 | Promotable.erase(User); |
164 | 6 | ToRemove.clear(); |
165 | 6 | |
166 | 1 | for (const PHINode *P : Promotable) { |
167 | 1 | // Condition 4 and 5 |
168 | 1 | const auto &Users = P->users(); |
169 | 1 | const auto &Operands = P->operands(); |
170 | 1 | if (!llvm::all_of(Users, IsPromotable) || |
171 | 1 | !llvm::all_of(Operands, IsPromotable)) |
172 | 1 | ToRemove.push_back(P); |
173 | 1 | } |
174 | 6 | } |
175 | 6.90k | |
176 | 6.90k | return Promotable; |
177 | 6.90k | } |
178 | | |
179 | | typedef DenseMap<Value *, Value *> B2IMap; |
180 | | |
181 | | public: |
182 | | static char ID; |
183 | | |
184 | 1.23k | PPCBoolRetToInt() : FunctionPass(ID) { |
185 | 1.23k | initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry()); |
186 | 1.23k | } |
187 | | |
188 | 6.90k | bool runOnFunction(Function &F) override { |
189 | 6.90k | if (skipFunction(F)) |
190 | 1 | return false; |
191 | 6.90k | |
192 | 6.90k | auto *TPC = getAnalysisIfAvailable<TargetPassConfig>(); |
193 | 6.90k | if (!TPC) |
194 | 0 | return false; |
195 | 6.90k | |
196 | 6.90k | auto &TM = TPC->getTM<PPCTargetMachine>(); |
197 | 6.90k | ST = TM.getSubtargetImpl(F); |
198 | 6.90k | |
199 | 6.90k | PHINodeSet PromotablePHINodes = getPromotablePHINodes(F); |
200 | 6.90k | B2IMap Bool2IntMap; |
201 | 6.90k | bool Changed = false; |
202 | 9.88k | for (auto &BB : F) { |
203 | 36.8k | for (auto &I : BB) { |
204 | 36.8k | if (auto *R = dyn_cast<ReturnInst>(&I)) |
205 | 6.97k | if (6.97k F.getReturnType()->isIntegerTy(1)6.97k ) |
206 | 60 | Changed |= |
207 | 60 | runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap); |
208 | 36.8k | |
209 | 36.8k | if (auto *CI = dyn_cast<CallInst>(&I)) |
210 | 2.42k | for (auto &U : CI->operands()) |
211 | 7.67k | if (7.67k U->getType()->isIntegerTy(1)7.67k ) |
212 | 80 | Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap); |
213 | 36.8k | } |
214 | 9.88k | } |
215 | 6.90k | |
216 | 6.90k | return Changed; |
217 | 6.90k | } |
218 | | |
219 | | bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes, |
220 | 140 | B2IMap &BoolToIntMap) { |
221 | 140 | auto Defs = findAllDefs(U); |
222 | 140 | |
223 | 140 | // If the values are all Constants or Arguments, don't bother |
224 | 140 | if (llvm::none_of(Defs, isa<Instruction, Value *>)) |
225 | 81 | return false; |
226 | 59 | |
227 | 59 | // Presently, we only know how to handle PHINode, Constant, Arguments and |
228 | 59 | // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign |
229 | 59 | // extension could also be handled in the future. |
230 | 59 | for (Value *V : Defs) |
231 | 86 | if (86 !isa<PHINode>(V) && 86 !isa<Constant>(V)71 && |
232 | 86 | !isa<Argument>(V)54 && !isa<CallInst>(V)50 ) |
233 | 49 | return false; |
234 | 10 | |
235 | 10 | for (Value *V : Defs) |
236 | 29 | if (const auto *29 P29 = dyn_cast<PHINode>(V)) |
237 | 14 | if (14 !PromotablePHINodes.count(P)14 ) |
238 | 2 | return false; |
239 | 8 | |
240 | 8 | if (8 isa<ReturnInst>(U.getUser())8 ) |
241 | 6 | ++NumBoolRetPromotion; |
242 | 8 | if (isa<CallInst>(U.getUser())) |
243 | 2 | ++NumBoolCallPromotion; |
244 | 8 | ++NumBoolToIntPromotion; |
245 | 8 | |
246 | 8 | for (Value *V : Defs) |
247 | 27 | if (27 !BoolToIntMap.count(V)27 ) |
248 | 23 | BoolToIntMap[V] = translate(V); |
249 | 8 | |
250 | 8 | // Replace the operands of the translated instructions. They were set to |
251 | 8 | // zero in the translate function. |
252 | 27 | for (auto &Pair : BoolToIntMap) { |
253 | 27 | auto *First = dyn_cast<User>(Pair.first); |
254 | 27 | auto *Second = dyn_cast<User>(Pair.second); |
255 | 27 | assert((!First || Second) && "translated from user to non-user!?"); |
256 | 27 | // Operands of CallInst are skipped because they may not be Bool type, |
257 | 27 | // and their positions are defined by ABI. |
258 | 27 | if (First && 27 !isa<CallInst>(First)25 ) |
259 | 47 | for (unsigned i = 0; 24 i < First->getNumOperands()47 ; ++i23 ) |
260 | 23 | Second->setOperand(i, BoolToIntMap[First->getOperand(i)]); |
261 | 27 | } |
262 | 140 | |
263 | 140 | Value *IntRetVal = BoolToIntMap[U]; |
264 | 140 | Type *Int1Ty = Type::getInt1Ty(U->getContext()); |
265 | 140 | auto *I = cast<Instruction>(U.getUser()); |
266 | 140 | Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I); |
267 | 140 | U.set(BackToBool); |
268 | 140 | |
269 | 140 | return true; |
270 | 140 | } |
271 | | |
272 | 1.23k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
273 | 1.23k | AU.addPreserved<DominatorTreeWrapperPass>(); |
274 | 1.23k | FunctionPass::getAnalysisUsage(AU); |
275 | 1.23k | } |
276 | | |
277 | | private: |
278 | | const PPCSubtarget *ST; |
279 | | }; |
280 | | |
281 | | } // end anonymous namespace |
282 | | |
283 | | char PPCBoolRetToInt::ID = 0; |
284 | | INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int", |
285 | | "Convert i1 constants to i32/i64 if they are returned", |
286 | | false, false) |
287 | | |
288 | 1.23k | FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); } |