LLVM 19.0.0git
PPCBoolRetToInt.cpp
Go to the documentation of this file.
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"
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"
48#include "llvm/IR/IRBuilder.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"
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) {
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:
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.
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
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
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
183 PPCBoolRetToInt() : FunctionPass(ID) {
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>(&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
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
273 void getAnalysisUsage(AnalysisUsage &AU) const override {
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(); }
ReachingDefAnalysis InstSet & ToRemove
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
iv Induction Variable Users
Definition: IVUsers.cpp:48
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
#define P(N)
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Target-Independent Code Generator Pass Configuration Options pass.
This defines the Use class.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
This class represents an Operation in the Expression.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2644
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Common code between 32-bit and 64-bit PowerPC targets.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt1Ty(LLVMContext &C)
static IntegerType * getInt64Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
NodeAddr< FuncNode * > Func
Definition: RDFGraph.h:393
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1731
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1745
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
void initializePPCBoolRetToIntPass(PassRegistry &)
FunctionPass * createPPCBoolRetToIntPass()