LLVM  15.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"
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 "ppc-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.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.
103  Value *Zero = Constant::getNullValue(IntTy);
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 
278 private:
279  const PPCSubtarget *ST;
280 };
281 
282 } // end anonymous namespace
283 
284 char PPCBoolRetToInt::ID = 0;
285 INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",
286  "Convert i1 constants to i32/i64 if they are returned", false,
287  false)
288 
289 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:236
llvm::none_of
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:1631
IntrinsicInst.h
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2089
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::SmallVector< Value *, 8 >
Statistic.h
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:542
llvm::createPPCBoolRetToIntPass
FunctionPass * createPPCBoolRetToIntPass()
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
Use.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:241
Instruction.h
llvm::all_of
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:1617
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
Constants.h
llvm::PPCSubtarget
Definition: PPCSubtarget.h:71
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
PPC.h
OperandTraits.h
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
SmallPtrSet.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::Use::set
void set(Value *Val)
Definition: Value.h:868
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4776
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2812
llvm::DenseMap
Definition: DenseMap.h:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
TargetPassConfig.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4815
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
Argument.h
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:240
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
INITIALIZE_PASS
INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int", "Convert i1 constants to i32/i64 if they are returned", false, false) FunctionPass *llvm
Definition: PPCBoolRetToInt.cpp:285
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PHINode::Create
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...
Definition: Instructions.h:2704
Casting.h
Function.h
llvm::PPCTargetMachine
Common code between 32-bit and 64-bit PowerPC targets.
Definition: PPCTargetMachine.h:25
Instructions.h
SmallVector.h
User.h
Dominators.h
llvm::initializePPCBoolRetToIntPass
void initializePPCBoolRetToIntPass(PassRegistry &)
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::PHINode
Definition: Instructions.h:2662
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:97
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
PPCTargetMachine.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
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
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38