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