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/IR/Argument.h"
42 #include "llvm/IR/Constants.h"
43 #include "llvm/IR/Dominators.h"
44 #include "llvm/IR/Function.h"
45 #include "llvm/IR/Instruction.h"
46 #include "llvm/IR/Instructions.h"
47 #include "llvm/IR/IntrinsicInst.h"
48 #include "llvm/IR/IRBuilder.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 "ppc-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 {
findAllDefs(Value * V)73 static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
74 SmallPtrSet<Value *, 8> Defs;
75 SmallVector<Value *, 8> WorkList;
76 WorkList.push_back(V);
77 Defs.insert(V);
78 while (!WorkList.empty()) {
79 Value *Curr = WorkList.pop_back_val();
80 auto *CurrUser = dyn_cast<User>(Curr);
81 // Operands of CallInst/Constant are skipped because they may not be Bool
82 // type. For CallInst, their positions are defined by ABI.
83 if (CurrUser && !isa<CallInst>(Curr) && !isa<Constant>(Curr))
84 for (auto &Op : CurrUser->operands())
85 if (Defs.insert(Op).second)
86 WorkList.push_back(Op);
87 }
88 return Defs;
89 }
90
91 // Translate a i1 value to an equivalent i32/i64 value:
translate(Value * V)92 Value *translate(Value *V) {
93 assert(V->getType() == Type::getInt1Ty(V->getContext()) &&
94 "Expect an i1 value");
95
96 Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
97 : Type::getInt32Ty(V->getContext());
98
99 if (auto *P = dyn_cast<PHINode>(V)) {
100 // Temporarily set the operands to 0. We'll fix this later in
101 // runOnUse.
102 Value *Zero = Constant::getNullValue(IntTy);
103 PHINode *Q =
104 PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P->getIterator());
105 for (unsigned i = 0; i < P->getNumOperands(); ++i)
106 Q->addIncoming(Zero, P->getIncomingBlock(i));
107 return Q;
108 }
109
110 IRBuilder IRB(V->getContext());
111 if (auto *I = dyn_cast<Instruction>(V))
112 IRB.SetInsertPoint(I->getNextNode());
113 else
114 IRB.SetInsertPoint(&Func->getEntryBlock(), Func->getEntryBlock().begin());
115 return IRB.CreateZExt(V, IntTy);
116 }
117
118 typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
119
120 // A PHINode is Promotable if:
121 // 1. Its type is i1 AND
122 // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
123 // AND
124 // 3. All of its operands are Constant or Argument or
125 // CallInst or PHINode AND
126 // 4. All of its PHINode uses are Promotable AND
127 // 5. All of its PHINode operands are Promotable
getPromotablePHINodes(const Function & F)128 static PHINodeSet getPromotablePHINodes(const Function &F) {
129 PHINodeSet Promotable;
130 // Condition 1
131 for (auto &BB : F)
132 for (auto &I : BB)
133 if (const auto *P = dyn_cast<PHINode>(&I))
134 if (P->getType()->isIntegerTy(1))
135 Promotable.insert(P);
136
137 SmallVector<const PHINode *, 8> ToRemove;
138 for (const PHINode *P : Promotable) {
139 // Condition 2 and 3
140 auto IsValidUser = [] (const Value *V) -> bool {
141 return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) ||
142 isa<DbgInfoIntrinsic>(V);
143 };
144 auto IsValidOperand = [] (const Value *V) -> bool {
145 return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||
146 isa<PHINode>(V);
147 };
148 const auto &Users = P->users();
149 const auto &Operands = P->operands();
150 if (!llvm::all_of(Users, IsValidUser) ||
151 !llvm::all_of(Operands, IsValidOperand))
152 ToRemove.push_back(P);
153 }
154
155 // Iterate to convergence
156 auto IsPromotable = [&Promotable] (const Value *V) -> bool {
157 const auto *Phi = dyn_cast<PHINode>(V);
158 return !Phi || Promotable.count(Phi);
159 };
160 while (!ToRemove.empty()) {
161 for (auto &User : ToRemove)
162 Promotable.erase(User);
163 ToRemove.clear();
164
165 for (const PHINode *P : Promotable) {
166 // Condition 4 and 5
167 const auto &Users = P->users();
168 const auto &Operands = P->operands();
169 if (!llvm::all_of(Users, IsPromotable) ||
170 !llvm::all_of(Operands, IsPromotable))
171 ToRemove.push_back(P);
172 }
173 }
174
175 return Promotable;
176 }
177
178 typedef DenseMap<Value *, Value *> B2IMap;
179
180 public:
181 static char ID;
182
PPCBoolRetToInt()183 PPCBoolRetToInt() : FunctionPass(ID) {
184 initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
185 }
186
runOnFunction(Function & F)187 bool runOnFunction(Function &F) override {
188 if (skipFunction(F))
189 return false;
190
191 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
192 if (!TPC)
193 return false;
194
195 auto &TM = TPC->getTM<PPCTargetMachine>();
196 ST = TM.getSubtargetImpl(F);
197 Func = &F;
198
199 PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
200 B2IMap Bool2IntMap;
201 bool Changed = false;
202 for (auto &BB : F) {
203 for (auto &I : BB) {
204 if (auto *R = dyn_cast<ReturnInst>(&I))
205 if (F.getReturnType()->isIntegerTy(1))
206 Changed |=
207 runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
208
209 if (auto *CI = dyn_cast<CallInst>(&I))
210 for (auto &U : CI->operands())
211 if (U->getType()->isIntegerTy(1))
212 Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
213 }
214 }
215
216 return Changed;
217 }
218
runOnUse(Use & U,const PHINodeSet & PromotablePHINodes,B2IMap & BoolToIntMap)219 bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
220 B2IMap &BoolToIntMap) {
221 auto Defs = findAllDefs(U);
222
223 // If the values are all Constants or Arguments, don't bother
224 if (llvm::none_of(Defs, [](Value *V) { return isa<Instruction>(V); }))
225 return false;
226
227 // Presently, we only know how to handle PHINode, Constant, Arguments and
228 // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign
229 // extension could also be handled in the future.
230 for (Value *V : Defs)
231 if (!isa<PHINode>(V) && !isa<Constant>(V) &&
232 !isa<Argument>(V) && !isa<CallInst>(V))
233 return false;
234
235 for (Value *V : Defs)
236 if (const auto *P = dyn_cast<PHINode>(V))
237 if (!PromotablePHINodes.count(P))
238 return false;
239
240 if (isa<ReturnInst>(U.getUser()))
241 ++NumBoolRetPromotion;
242 if (isa<CallInst>(U.getUser()))
243 ++NumBoolCallPromotion;
244 ++NumBoolToIntPromotion;
245
246 for (Value *V : Defs)
247 if (!BoolToIntMap.count(V))
248 BoolToIntMap[V] = translate(V);
249
250 // Replace the operands of the translated instructions. They were set to
251 // zero in the translate function.
252 for (auto &Pair : BoolToIntMap) {
253 auto *First = dyn_cast<User>(Pair.first);
254 auto *Second = dyn_cast<User>(Pair.second);
255 assert((!First || Second) && "translated from user to non-user!?");
256 // Operands of CallInst/Constant are skipped because they may not be Bool
257 // type. For CallInst, their positions are defined by ABI.
258 if (First && !isa<CallInst>(First) && !isa<Constant>(First))
259 for (unsigned i = 0; i < First->getNumOperands(); ++i)
260 Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
261 }
262
263 Value *IntRetVal = BoolToIntMap[U];
264 Type *Int1Ty = Type::getInt1Ty(U->getContext());
265 auto *I = cast<Instruction>(U.getUser());
266 Value *BackToBool =
267 new TruncInst(IntRetVal, Int1Ty, "backToBool", I->getIterator());
268 U.set(BackToBool);
269
270 return true;
271 }
272
getAnalysisUsage(AnalysisUsage & AU) const273 void getAnalysisUsage(AnalysisUsage &AU) const override {
274 AU.addPreserved<DominatorTreeWrapperPass>();
275 FunctionPass::getAnalysisUsage(AU);
276 }
277
278 private:
279 const PPCSubtarget *ST;
280 Function *Func;
281 };
282
283 } // end anonymous namespace
284
285 char PPCBoolRetToInt::ID = 0;
286 INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",
287 "Convert i1 constants to i32/i64 if they are returned", false,
288 false)
289
createPPCBoolRetToIntPass()290 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
291