LLVM 17.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"
49#include "llvm/IR/Type.h"
50#include "llvm/IR/Use.h"
51#include "llvm/IR/User.h"
52#include "llvm/IR/Value.h"
53#include "llvm/Pass.h"
56#include <cassert>
57
58using namespace llvm;
59
60namespace {
61
62#define DEBUG_TYPE "ppc-bool-ret-to-int"
63
64STATISTIC(NumBoolRetPromotion,
65 "Number of times a bool feeding a RetInst was promoted to an int");
66STATISTIC(NumBoolCallPromotion,
67 "Number of times a bool feeding a CallInst was promoted to an int");
68STATISTIC(NumBoolToIntPromotion,
69 "Total number of times a bool was promoted to an int");
70
71class PPCBoolRetToInt : public FunctionPass {
72 static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
75 WorkList.push_back(V);
76 Defs.insert(V);
77 while (!WorkList.empty()) {
78 Value *Curr = WorkList.pop_back_val();
79 auto *CurrUser = dyn_cast<User>(Curr);
80 // Operands of CallInst/Constant are skipped because they may not be Bool
81 // type. For CallInst, their positions are defined by ABI.
82 if (CurrUser && !isa<CallInst>(Curr) && !isa<Constant>(Curr))
83 for (auto &Op : CurrUser->operands())
84 if (Defs.insert(Op).second)
85 WorkList.push_back(Op);
86 }
87 return Defs;
88 }
89
90 // Translate a i1 value to an equivalent i32/i64 value:
91 Value *translate(Value *V) {
92 assert(V->getType() == Type::getInt1Ty(V->getContext()) &&
93 "Expect an i1 value");
94
95 Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
96 : Type::getInt32Ty(V->getContext());
97
98 if (auto *C = dyn_cast<Constant>(V))
99 return ConstantExpr::getZExt(C, IntTy);
100 if (auto *P = dyn_cast<PHINode>(V)) {
101 // Temporarily set the operands to 0. We'll fix this later in
102 // runOnUse.
104 PHINode *Q =
105 PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P);
106 for (unsigned i = 0; i < P->getNumOperands(); ++i)
107 Q->addIncoming(Zero, P->getIncomingBlock(i));
108 return Q;
109 }
110
111 auto *A = dyn_cast<Argument>(V);
112 auto *I = dyn_cast<Instruction>(V);
113 assert((A || I) && "Unknown value type");
114
115 auto InstPt =
116 A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode();
117 return new ZExtInst(V, IntTy, "", InstPt);
118 }
119
120 typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
121
122 // A PHINode is Promotable if:
123 // 1. Its type is i1 AND
124 // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
125 // AND
126 // 3. All of its operands are Constant or Argument or
127 // CallInst or PHINode AND
128 // 4. All of its PHINode uses are Promotable AND
129 // 5. All of its PHINode operands are Promotable
130 static PHINodeSet getPromotablePHINodes(const Function &F) {
131 PHINodeSet Promotable;
132 // Condition 1
133 for (auto &BB : F)
134 for (auto &I : BB)
135 if (const auto *P = dyn_cast<PHINode>(&I))
136 if (P->getType()->isIntegerTy(1))
137 Promotable.insert(P);
138
140 for (const PHINode *P : Promotable) {
141 // Condition 2 and 3
142 auto IsValidUser = [] (const Value *V) -> bool {
143 return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) ||
144 isa<DbgInfoIntrinsic>(V);
145 };
146 auto IsValidOperand = [] (const Value *V) -> bool {
147 return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||
148 isa<PHINode>(V);
149 };
150 const auto &Users = P->users();
151 const auto &Operands = P->operands();
152 if (!llvm::all_of(Users, IsValidUser) ||
153 !llvm::all_of(Operands, IsValidOperand))
154 ToRemove.push_back(P);
155 }
156
157 // Iterate to convergence
158 auto IsPromotable = [&Promotable] (const Value *V) -> bool {
159 const auto *Phi = dyn_cast<PHINode>(V);
160 return !Phi || Promotable.count(Phi);
161 };
162 while (!ToRemove.empty()) {
163 for (auto &User : ToRemove)
164 Promotable.erase(User);
165 ToRemove.clear();
166
167 for (const PHINode *P : Promotable) {
168 // Condition 4 and 5
169 const auto &Users = P->users();
170 const auto &Operands = P->operands();
171 if (!llvm::all_of(Users, IsPromotable) ||
172 !llvm::all_of(Operands, IsPromotable))
173 ToRemove.push_back(P);
174 }
175 }
176
177 return Promotable;
178 }
179
180 typedef DenseMap<Value *, Value *> B2IMap;
181
182 public:
183 static char ID;
184
185 PPCBoolRetToInt() : FunctionPass(ID) {
187 }
188
189 bool runOnFunction(Function &F) override {
190 if (skipFunction(F))
191 return false;
192
193 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
194 if (!TPC)
195 return false;
196
197 auto &TM = TPC->getTM<PPCTargetMachine>();
198 ST = TM.getSubtargetImpl(F);
199
200 PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
201 B2IMap Bool2IntMap;
202 bool Changed = false;
203 for (auto &BB : F) {
204 for (auto &I : BB) {
205 if (auto *R = dyn_cast<ReturnInst>(&I))
206 if (F.getReturnType()->isIntegerTy(1))
207 Changed |=
208 runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
209
210 if (auto *CI = dyn_cast<CallInst>(&I))
211 for (auto &U : CI->operands())
212 if (U->getType()->isIntegerTy(1))
213 Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
214 }
215 }
216
217 return Changed;
218 }
219
220 bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
221 B2IMap &BoolToIntMap) {
222 auto Defs = findAllDefs(U);
223
224 // If the values are all Constants or Arguments, don't bother
225 if (llvm::none_of(Defs, [](Value *V) { return isa<Instruction>(V); }))
226 return false;
227
228 // Presently, we only know how to handle PHINode, Constant, Arguments and
229 // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign
230 // extension could also be handled in the future.
231 for (Value *V : Defs)
232 if (!isa<PHINode>(V) && !isa<Constant>(V) &&
233 !isa<Argument>(V) && !isa<CallInst>(V))
234 return false;
235
236 for (Value *V : Defs)
237 if (const auto *P = dyn_cast<PHINode>(V))
238 if (!PromotablePHINodes.count(P))
239 return false;
240
241 if (isa<ReturnInst>(U.getUser()))
242 ++NumBoolRetPromotion;
243 if (isa<CallInst>(U.getUser()))
244 ++NumBoolCallPromotion;
245 ++NumBoolToIntPromotion;
246
247 for (Value *V : Defs)
248 if (!BoolToIntMap.count(V))
249 BoolToIntMap[V] = translate(V);
250
251 // Replace the operands of the translated instructions. They were set to
252 // zero in the translate function.
253 for (auto &Pair : BoolToIntMap) {
254 auto *First = dyn_cast<User>(Pair.first);
255 auto *Second = dyn_cast<User>(Pair.second);
256 assert((!First || Second) && "translated from user to non-user!?");
257 // Operands of CallInst/Constant are skipped because they may not be Bool
258 // type. For CallInst, their positions are defined by ABI.
259 if (First && !isa<CallInst>(First) && !isa<Constant>(First))
260 for (unsigned i = 0; i < First->getNumOperands(); ++i)
261 Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
262 }
263
264 Value *IntRetVal = BoolToIntMap[U];
265 Type *Int1Ty = Type::getInt1Ty(U->getContext());
266 auto *I = cast<Instruction>(U.getUser());
267 Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
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};
281
282} // end anonymous namespace
283
284char PPCBoolRetToInt::ID = 0;
285INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",
286 "Convert i1 constants to i32/i64 if they are returned", false,
287 false)
288
289FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
ReachingDefAnalysis InstSet & ToRemove
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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 * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2118
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:174
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="", Instruction *InsertBefore=nullptr)
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:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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
This class represents zero extension of integer types.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
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:1782
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:1796
void initializePPCBoolRetToIntPass(PassRegistry &)
FunctionPass * createPPCBoolRetToIntPass()