LLVM  6.0.0svn
PPCBoolRetToInt.cpp
Go to the documentation of this file.
1 //===- PPCBoolRetToInt.cpp ------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements converting i1 values to i32/i64 if they could be more
11 // profitably allocated as GPRs rather than CRs. This pass will become totally
12 // unnecessary if Register Bank Allocation and Global Instruction Selection ever
13 // go upstream.
14 //
15 // Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the
16 // transitive closure of their uses includes only PHINodes, CallInsts, and
17 // ReturnInsts. The rational is that arguments are generally passed and returned
18 // in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will
19 // actually save casts at the Machine Instruction level.
20 //
21 // It might be useful to expand this pass to add bit-wise operations to the list
22 // of safe transitive closure types. Also, we miss some opportunities when LLVM
23 // represents logical AND and OR operations with control flow rather than data
24 // flow. For example by lowering the expression: return (A && B && C)
25 //
26 // as: return A ? true : B && C.
27 //
28 // There's code in SimplifyCFG that code be used to turn control flow in data
29 // flow using SelectInsts. Selects are slow on some architectures (P7/P8), so
30 // this probably isn't good in general, but for the special case of i1, the
31 // Selects could be further lowered to bit operations that are fast everywhere.
32 //
33 //===----------------------------------------------------------------------===//
34 
35 #include "PPC.h"
36 #include "PPCTargetMachine.h"
37 #include "llvm/ADT/DenseMap.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/ADT/Statistic.h"
42 #include "llvm/IR/Argument.h"
43 #include "llvm/IR/Constants.h"
44 #include "llvm/IR/Dominators.h"
45 #include "llvm/IR/Function.h"
46 #include "llvm/IR/Instruction.h"
47 #include "llvm/IR/Instructions.h"
48 #include "llvm/IR/IntrinsicInst.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"
56 #include "llvm/Support/Casting.h"
57 #include <cassert>
58 
59 using namespace llvm;
60 
61 namespace {
62 
63 #define DEBUG_TYPE "bool-ret-to-int"
64 
65 STATISTIC(NumBoolRetPromotion,
66  "Number of times a bool feeding a RetInst was promoted to an int");
67 STATISTIC(NumBoolCallPromotion,
68  "Number of times a bool feeding a CallInst was promoted to an int");
69 STATISTIC(NumBoolToIntPromotion,
70  "Total number of times a bool was promoted to an int");
71 
72 class PPCBoolRetToInt : public FunctionPass {
73  static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
75  SmallVector<Value *, 8> WorkList;
76  WorkList.push_back(V);
77  Defs.insert(V);
78  while (!WorkList.empty()) {
79  Value *Curr = WorkList.back();
80  WorkList.pop_back();
81  auto *CurrUser = dyn_cast<User>(Curr);
82  // Operands of CallInst are skipped because they may not be Bool type,
83  // and their positions are defined by ABI.
84  if (CurrUser && !isa<CallInst>(Curr))
85  for (auto &Op : CurrUser->operands())
86  if (Defs.insert(Op).second)
87  WorkList.push_back(Op);
88  }
89  return Defs;
90  }
91 
92  // Translate a i1 value to an equivalent i32/i64 value:
93  Value *translate(Value *V) {
94  Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())
96 
97  if (auto *C = dyn_cast<Constant>(V))
98  return ConstantExpr::getZExt(C, IntTy);
99  if (auto *P = dyn_cast<PHINode>(V)) {
100  // Temporarily set the operands to 0. We'll fix this later in
101  // runOnUse.
102  Value *Zero = Constant::getNullValue(IntTy);
103  PHINode *Q =
104  PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P);
105  for (unsigned i = 0; i < P->getNumOperands(); ++i)
106  Q->addIncoming(Zero, P->getIncomingBlock(i));
107  return Q;
108  }
109 
110  auto *A = dyn_cast<Argument>(V);
111  auto *I = dyn_cast<Instruction>(V);
112  assert((A || I) && "Unknown value type");
113 
114  auto InstPt =
115  A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode();
116  return new ZExtInst(V, IntTy, "", InstPt);
117  }
118 
119  typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
120 
121  // A PHINode is Promotable if:
122  // 1. Its type is i1 AND
123  // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
124  // AND
125  // 3. All of its operands are Constant or Argument or
126  // CallInst or PHINode AND
127  // 4. All of its PHINode uses are Promotable AND
128  // 5. All of its PHINode operands are Promotable
129  static PHINodeSet getPromotablePHINodes(const Function &F) {
130  PHINodeSet Promotable;
131  // Condition 1
132  for (auto &BB : F)
133  for (auto &I : BB)
134  if (const auto *P = dyn_cast<PHINode>(&I))
135  if (P->getType()->isIntegerTy(1))
136  Promotable.insert(P);
137 
139  for (const PHINode *P : Promotable) {
140  // Condition 2 and 3
141  auto IsValidUser = [] (const Value *V) -> bool {
142  return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) ||
143  isa<DbgInfoIntrinsic>(V);
144  };
145  auto IsValidOperand = [] (const Value *V) -> bool {
146  return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||
147  isa<PHINode>(V);
148  };
149  const auto &Users = P->users();
150  const auto &Operands = P->operands();
151  if (!llvm::all_of(Users, IsValidUser) ||
152  !llvm::all_of(Operands, IsValidOperand))
153  ToRemove.push_back(P);
154  }
155 
156  // Iterate to convergence
157  auto IsPromotable = [&Promotable] (const Value *V) -> bool {
158  const auto *Phi = dyn_cast<PHINode>(V);
159  return !Phi || Promotable.count(Phi);
160  };
161  while (!ToRemove.empty()) {
162  for (auto &User : ToRemove)
163  Promotable.erase(User);
164  ToRemove.clear();
165 
166  for (const PHINode *P : Promotable) {
167  // Condition 4 and 5
168  const auto &Users = P->users();
169  const auto &Operands = P->operands();
170  if (!llvm::all_of(Users, IsPromotable) ||
171  !llvm::all_of(Operands, IsPromotable))
172  ToRemove.push_back(P);
173  }
174  }
175 
176  return Promotable;
177  }
178 
179  typedef DenseMap<Value *, Value *> B2IMap;
180 
181  public:
182  static char ID;
183 
184  PPCBoolRetToInt() : FunctionPass(ID) {
186  }
187 
188  bool runOnFunction(Function &F) override {
189  if (skipFunction(F))
190  return false;
191 
192  auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
193  if (!TPC)
194  return false;
195 
196  auto &TM = TPC->getTM<PPCTargetMachine>();
197  ST = TM.getSubtargetImpl(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, isa<Instruction, Value *>))
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 are skipped because they may not be Bool type,
257  // and their positions are defined by ABI.
258  if (First && !isa<CallInst>(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 = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
267  U.set(BackToBool);
268 
269  return true;
270  }
271 
272  void getAnalysisUsage(AnalysisUsage &AU) const override {
275  }
276 
277 private:
278  const PPCSubtarget *ST;
279 };
280 
281 } // end anonymous namespace
282 
283 char PPCBoolRetToInt::ID = 0;
284 INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
285  "Convert i1 constants to i32/i64 if they are returned",
286  false, false)
287 
288 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
uint64_t CallInst * C
void push_back(const T &Elt)
Definition: SmallVector.h:212
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
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:30
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This class represents zero extension of integer types.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:728
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:813
STATISTIC(NumFunctions, "Total number of functions")
F(f)
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:177
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:207
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
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:827
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1570
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:91
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:671
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
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:371
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
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:418
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:176
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#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:323
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:267