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