LLVM  10.0.0svn
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"
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/OperandTraits.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"
55 #include "llvm/Support/Casting.h"
56 #include <cassert>
57 
58 using namespace llvm;
59 
60 namespace {
61 
62 #define DEBUG_TYPE "bool-ret-to-int"
63 
64 STATISTIC(NumBoolRetPromotion,
65  "Number of times a bool feeding a RetInst was promoted to an int");
66 STATISTIC(NumBoolCallPromotion,
67  "Number of times a bool feeding a CallInst was promoted to an int");
68 STATISTIC(NumBoolToIntPromotion,
69  "Total number of times a bool was promoted to an int");
70 
71 class PPCBoolRetToInt : public FunctionPass {
72  static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
74  SmallVector<Value *, 8> WorkList;
75  WorkList.push_back(V);
76  Defs.insert(V);
77  while (!WorkList.empty()) {
78  Value *Curr = WorkList.back();
79  WorkList.pop_back();
80  auto *CurrUser = dyn_cast<User>(Curr);
81  // Operands of CallInst are skipped because they may not be Bool type,
82  // and their positions are defined by ABI.
83  if (CurrUser && !isa<CallInst>(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  Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
95 
96  if (auto *C = dyn_cast<Constant>(V))
97  return ConstantExpr::getZExt(C, IntTy);
98  if (auto *P = dyn_cast<PHINode>(V)) {
99  // Temporarily set the operands to 0. We'll fix this later in
100  // runOnUse.
101  Value *Zero = Constant::getNullValue(IntTy);
102  PHINode *Q =
103  PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P);
104  for (unsigned i = 0; i < P->getNumOperands(); ++i)
105  Q->addIncoming(Zero, P->getIncomingBlock(i));
106  return Q;
107  }
108 
109  auto *A = dyn_cast<Argument>(V);
110  auto *I = dyn_cast<Instruction>(V);
111  assert((A || I) && "Unknown value type");
112 
113  auto InstPt =
114  A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode();
115  return new ZExtInst(V, IntTy, "", InstPt);
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 
198  PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
199  B2IMap Bool2IntMap;
200  bool Changed = false;
201  for (auto &BB : F) {
202  for (auto &I : BB) {
203  if (auto *R = dyn_cast<ReturnInst>(&I))
204  if (F.getReturnType()->isIntegerTy(1))
205  Changed |=
206  runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
207 
208  if (auto *CI = dyn_cast<CallInst>(&I))
209  for (auto &U : CI->operands())
210  if (U->getType()->isIntegerTy(1))
211  Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
212  }
213  }
214 
215  return Changed;
216  }
217 
218  bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
219  B2IMap &BoolToIntMap) {
220  auto Defs = findAllDefs(U);
221 
222  // If the values are all Constants or Arguments, don't bother
223  if (llvm::none_of(Defs, isa<Instruction, Value *>))
224  return false;
225 
226  // Presently, we only know how to handle PHINode, Constant, Arguments and
227  // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign
228  // extension could also be handled in the future.
229  for (Value *V : Defs)
230  if (!isa<PHINode>(V) && !isa<Constant>(V) &&
231  !isa<Argument>(V) && !isa<CallInst>(V))
232  return false;
233 
234  for (Value *V : Defs)
235  if (const auto *P = dyn_cast<PHINode>(V))
236  if (!PromotablePHINodes.count(P))
237  return false;
238 
239  if (isa<ReturnInst>(U.getUser()))
240  ++NumBoolRetPromotion;
241  if (isa<CallInst>(U.getUser()))
242  ++NumBoolCallPromotion;
243  ++NumBoolToIntPromotion;
244 
245  for (Value *V : Defs)
246  if (!BoolToIntMap.count(V))
247  BoolToIntMap[V] = translate(V);
248 
249  // Replace the operands of the translated instructions. They were set to
250  // zero in the translate function.
251  for (auto &Pair : BoolToIntMap) {
252  auto *First = dyn_cast<User>(Pair.first);
253  auto *Second = dyn_cast<User>(Pair.second);
254  assert((!First || Second) && "translated from user to non-user!?");
255  // Operands of CallInst are skipped because they may not be Bool type,
256  // and their positions are defined by ABI.
257  if (First && !isa<CallInst>(First))
258  for (unsigned i = 0; i < First->getNumOperands(); ++i)
259  Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
260  }
261 
262  Value *IntRetVal = BoolToIntMap[U];
263  Type *Int1Ty = Type::getInt1Ty(U->getContext());
264  auto *I = cast<Instruction>(U.getUser());
265  Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
266  U.set(BackToBool);
267 
268  return true;
269  }
270 
271  void getAnalysisUsage(AnalysisUsage &AU) const override {
274  }
275 
276 private:
277  const PPCSubtarget *ST;
278 };
279 
280 } // end anonymous namespace
281 
282 char PPCBoolRetToInt::ID = 0;
283 INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
284  "Convert i1 constants to i32/i64 if they are returned",
285  false, false)
286 
287 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
uint64_t CallInst * C
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:172
INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int", "Convert i1 constants to i32/i64 if they are returned", false, false) FunctionPass *llvm
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This class represents zero extension of integer types.
void push_back(const T &Elt)
Definition: SmallVector.h:211
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:733
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:1165
STATISTIC(NumFunctions, "Total number of functions")
F(f)
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:176
iv Induction Variable Users
Definition: IVUsers.cpp:51
This defines the Use class.
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
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:1179
mir Rename Register Operands
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1696
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:96
FunctionPass * createPPCBoolRetToIntPass()
This class represents a truncation of integer types.
void initializePPCBoolRetToIntPass(PassRegistry &)
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
void set(Value *Val)
Definition: Value.h:719
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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:370
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
Common code between 32-bit and 64-bit PowerPC targets.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259