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
59using namespace llvm;
60
61namespace {
62
63#define DEBUG_TYPE "ppc-bool-ret-to-int"
64
65STATISTIC(NumBoolRetPromotion,
66 "Number of times a bool feeding a RetInst was promoted to an int");
67STATISTIC(NumBoolCallPromotion,
68 "Number of times a bool feeding a CallInst was promoted to an int");
69STATISTIC(NumBoolToIntPromotion,
70 "Total number of times a bool was promoted to an int");
71
72class PPCBoolRetToInt : public FunctionPass {
73 static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
74 SmallPtrSet<Value *, 8> Defs;
75 SmallVector<Value *, 8> WorkList;
76 WorkList.push_back(Elt: V);
77 Defs.insert(Ptr: V);
78 while (!WorkList.empty()) {
79 Value *Curr = WorkList.pop_back_val();
80 auto *CurrUser = dyn_cast<User>(Val: 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>(Val: Curr) && !isa<Constant>(Val: Curr))
84 for (auto &Op : CurrUser->operands())
85 if (Defs.insert(Ptr: Op).second)
86 WorkList.push_back(Elt: Op);
87 }
88 return Defs;
89 }
90
91 // Translate a i1 value to an equivalent i32/i64 value:
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(C&: V->getContext())
97 : Type::getInt32Ty(C&: V->getContext());
98
99 if (auto *P = dyn_cast<PHINode>(Val: V)) {
100 // Temporarily set the operands to 0. We'll fix this later in
101 // runOnUse.
102 Value *Zero = Constant::getNullValue(Ty: IntTy);
103 PHINode *Q =
104 PHINode::Create(Ty: IntTy, NumReservedValues: P->getNumIncomingValues(), NameStr: P->getName(), InsertBefore: P->getIterator());
105 for (unsigned i = 0; i < P->getNumOperands(); ++i)
106 Q->addIncoming(V: Zero, BB: P->getIncomingBlock(i));
107 return Q;
108 }
109
110 IRBuilder IRB(V->getContext());
111 if (auto *I = dyn_cast<Instruction>(Val: V))
112 IRB.SetInsertPoint(I->getNextNode());
113 else
114 IRB.SetInsertPoint(TheBB: &Func->getEntryBlock(), IP: Func->getEntryBlock().begin());
115 return IRB.CreateZExt(V, DestTy: 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
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>(Val: &I))
134 if (P->getType()->isIntegerTy(Bitwidth: 1))
135 Promotable.insert(Ptr: 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>(Val: V) || isa<CallInst>(Val: V) || isa<PHINode>(Val: V) ||
142 isa<DbgInfoIntrinsic>(Val: V);
143 };
144 auto IsValidOperand = [] (const Value *V) -> bool {
145 return isa<Constant>(Val: V) || isa<Argument>(Val: V) || isa<CallInst>(Val: V) ||
146 isa<PHINode>(Val: V);
147 };
148 const auto &Users = P->users();
149 const auto &Operands = P->operands();
150 if (!llvm::all_of(Range: Users, P: IsValidUser) ||
151 !llvm::all_of(Range: Operands, P: IsValidOperand))
152 ToRemove.push_back(Elt: P);
153 }
154
155 // Iterate to convergence
156 auto IsPromotable = [&Promotable] (const Value *V) -> bool {
157 const auto *Phi = dyn_cast<PHINode>(Val: V);
158 return !Phi || Promotable.count(Ptr: Phi);
159 };
160 while (!ToRemove.empty()) {
161 for (auto &User : ToRemove)
162 Promotable.erase(Ptr: 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(Range: Users, P: IsPromotable) ||
170 !llvm::all_of(Range: Operands, P: IsPromotable))
171 ToRemove.push_back(Elt: P);
172 }
173 }
174
175 return Promotable;
176 }
177
178 typedef DenseMap<Value *, Value *> B2IMap;
179
180 public:
181 static char ID;
182
183 PPCBoolRetToInt() : FunctionPass(ID) {
184 initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
185 }
186
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>(Val: &I))
205 if (F.getReturnType()->isIntegerTy(Bitwidth: 1))
206 Changed |=
207 runOnUse(U&: R->getOperandUse(i: 0), PromotablePHINodes, BoolToIntMap&: Bool2IntMap);
208
209 if (auto *CI = dyn_cast<CallInst>(Val: &I))
210 for (auto &U : CI->operands())
211 if (U->getType()->isIntegerTy(Bitwidth: 1))
212 Changed |= runOnUse(U, PromotablePHINodes, BoolToIntMap&: Bool2IntMap);
213 }
214 }
215
216 return Changed;
217 }
218
219 bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
220 B2IMap &BoolToIntMap) {
221 auto Defs = findAllDefs(V: U);
222
223 // If the values are all Constants or Arguments, don't bother
224 if (llvm::none_of(Range&: Defs, P: [](Value *V) { return isa<Instruction>(Val: 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>(Val: V) && !isa<Constant>(Val: V) &&
232 !isa<Argument>(Val: V) && !isa<CallInst>(Val: V))
233 return false;
234
235 for (Value *V : Defs)
236 if (const auto *P = dyn_cast<PHINode>(Val: V))
237 if (!PromotablePHINodes.count(Ptr: P))
238 return false;
239
240 if (isa<ReturnInst>(Val: U.getUser()))
241 ++NumBoolRetPromotion;
242 if (isa<CallInst>(Val: U.getUser()))
243 ++NumBoolCallPromotion;
244 ++NumBoolToIntPromotion;
245
246 for (Value *V : Defs)
247 if (!BoolToIntMap.count(Val: 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>(Val: Pair.first);
254 auto *Second = dyn_cast<User>(Val: 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>(Val: First) && !isa<Constant>(Val: First))
259 for (unsigned i = 0; i < First->getNumOperands(); ++i)
260 Second->setOperand(i, Val: BoolToIntMap[First->getOperand(i)]);
261 }
262
263 Value *IntRetVal = BoolToIntMap[U];
264 Type *Int1Ty = Type::getInt1Ty(C&: U->getContext());
265 auto *I = cast<Instruction>(Val: U.getUser());
266 Value *BackToBool =
267 new TruncInst(IntRetVal, Int1Ty, "backToBool", I->getIterator());
268 U.set(BackToBool);
269
270 return true;
271 }
272
273 void getAnalysisUsage(AnalysisUsage &AU) const override {
274 AU.addPreserved<DominatorTreeWrapperPass>();
275 FunctionPass::getAnalysisUsage(AU);
276 }
277
278private:
279 const PPCSubtarget *ST;
280 Function *Func;
281};
282
283} // end anonymous namespace
284
285char PPCBoolRetToInt::ID = 0;
286INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",
287 "Convert i1 constants to i32/i64 if they are returned", false,
288 false)
289
290FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
291