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"
54 #include "llvm/CodeGen/TargetPassConfig.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) {
73     SmallPtrSet<Value *, 8> Defs;
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 
139     SmallVector<const PHINode *, 8> ToRemove;
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) {
186     initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
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 {
274     AU.addPreserved<DominatorTreeWrapperPass>();
275     FunctionPass::getAnalysisUsage(AU);
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(); }
290