• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- PPCBoolRetToInt.cpp - Convert bool literals to i32 if they are returned ==//
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 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 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 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 "llvm/Transforms/Scalar.h"
37 #include "llvm/ADT/SmallPtrSet.h"
38 #include "llvm/ADT/Statistic.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Instructions.h"
42 #include "llvm/IR/IntrinsicInst.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "llvm/Pass.h"
45 
46 using namespace llvm;
47 
48 namespace {
49 
50 #define DEBUG_TYPE "bool-ret-to-int"
51 
52 STATISTIC(NumBoolRetPromotion,
53           "Number of times a bool feeding a RetInst was promoted to an int");
54 STATISTIC(NumBoolCallPromotion,
55           "Number of times a bool feeding a CallInst was promoted to an int");
56 STATISTIC(NumBoolToIntPromotion,
57           "Total number of times a bool was promoted to an int");
58 
59 class PPCBoolRetToInt : public FunctionPass {
60 
findAllDefs(Value * V)61   static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {
62     SmallPtrSet<Value *, 8> Defs;
63     SmallVector<Value *, 8> WorkList;
64     WorkList.push_back(V);
65     Defs.insert(V);
66     while (!WorkList.empty()) {
67       Value *Curr = WorkList.back();
68       WorkList.pop_back();
69       if (User *CurrUser = dyn_cast<User>(Curr))
70         for (auto &Op : CurrUser->operands())
71           if (Defs.insert(Op).second)
72             WorkList.push_back(Op);
73     }
74     return Defs;
75   }
76 
77   // Translate a i1 value to an equivalent i32 value:
translate(Value * V)78   static Value *translate(Value *V) {
79     Type *Int32Ty = Type::getInt32Ty(V->getContext());
80     if (Constant *C = dyn_cast<Constant>(V))
81       return ConstantExpr::getZExt(C, Int32Ty);
82     if (PHINode *P = dyn_cast<PHINode>(V)) {
83       // Temporarily set the operands to 0. We'll fix this later in
84       // runOnUse.
85       Value *Zero = Constant::getNullValue(Int32Ty);
86       PHINode *Q =
87         PHINode::Create(Int32Ty, P->getNumIncomingValues(), P->getName(), P);
88       for (unsigned i = 0; i < P->getNumOperands(); ++i)
89         Q->addIncoming(Zero, P->getIncomingBlock(i));
90       return Q;
91     }
92 
93     Argument *A = dyn_cast<Argument>(V);
94     Instruction *I = dyn_cast<Instruction>(V);
95     assert((A || I) && "Unknown value type");
96 
97     auto InstPt =
98       A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode();
99     return new ZExtInst(V, Int32Ty, "", InstPt);
100   }
101 
102   typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;
103 
104   // A PHINode is Promotable if:
105   // 1. Its type is i1 AND
106   // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic
107   // AND
108   // 3. All of its operands are Constant or Argument or
109   //    CallInst or PHINode AND
110   // 4. All of its PHINode uses are Promotable AND
111   // 5. All of its PHINode operands are Promotable
getPromotablePHINodes(const Function & F)112   static PHINodeSet getPromotablePHINodes(const Function &F) {
113     PHINodeSet Promotable;
114     // Condition 1
115     for (auto &BB : F)
116       for (auto &I : BB)
117         if (const PHINode *P = dyn_cast<PHINode>(&I))
118           if (P->getType()->isIntegerTy(1))
119             Promotable.insert(P);
120 
121     SmallVector<const PHINode *, 8> ToRemove;
122     for (const PHINode *P : Promotable) {
123       // Condition 2 and 3
124       auto IsValidUser = [] (const Value *V) -> bool {
125         return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) ||
126         isa<DbgInfoIntrinsic>(V);
127       };
128       auto IsValidOperand = [] (const Value *V) -> bool {
129         return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||
130         isa<PHINode>(V);
131       };
132       const auto &Users = P->users();
133       const auto &Operands = P->operands();
134       if (!std::all_of(Users.begin(), Users.end(), IsValidUser) ||
135           !std::all_of(Operands.begin(), Operands.end(), IsValidOperand))
136         ToRemove.push_back(P);
137     }
138 
139     // Iterate to convergence
140     auto IsPromotable = [&Promotable] (const Value *V) -> bool {
141       const PHINode *Phi = dyn_cast<PHINode>(V);
142       return !Phi || Promotable.count(Phi);
143     };
144     while (!ToRemove.empty()) {
145       for (auto &User : ToRemove)
146         Promotable.erase(User);
147       ToRemove.clear();
148 
149       for (const PHINode *P : Promotable) {
150         // Condition 4 and 5
151         const auto &Users = P->users();
152         const auto &Operands = P->operands();
153         if (!std::all_of(Users.begin(), Users.end(), IsPromotable) ||
154             !std::all_of(Operands.begin(), Operands.end(), IsPromotable))
155           ToRemove.push_back(P);
156       }
157     }
158 
159     return Promotable;
160   }
161 
162   typedef DenseMap<Value *, Value *> B2IMap;
163 
164  public:
165   static char ID;
PPCBoolRetToInt()166   PPCBoolRetToInt() : FunctionPass(ID) {
167     initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
168   }
169 
runOnFunction(Function & F)170   bool runOnFunction(Function &F) {
171     if (skipFunction(F))
172       return false;
173 
174     PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
175     B2IMap Bool2IntMap;
176     bool Changed = false;
177     for (auto &BB : F) {
178       for (auto &I : BB) {
179         if (ReturnInst *R = dyn_cast<ReturnInst>(&I))
180           if (F.getReturnType()->isIntegerTy(1))
181             Changed |=
182               runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
183 
184         if (CallInst *CI = dyn_cast<CallInst>(&I))
185           for (auto &U : CI->operands())
186             if (U->getType()->isIntegerTy(1))
187               Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
188       }
189     }
190 
191     return Changed;
192   }
193 
runOnUse(Use & U,const PHINodeSet & PromotablePHINodes,B2IMap & BoolToIntMap)194   static bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
195                        B2IMap &BoolToIntMap) {
196     auto Defs = findAllDefs(U);
197 
198     // If the values are all Constants or Arguments, don't bother
199     if (!std::any_of(Defs.begin(), Defs.end(), isa<Instruction, Value *>))
200       return false;
201 
202     // Presently, we only know how to handle PHINode, Constant, and Arguments.
203     // Potentially, bitwise operations (AND, OR, XOR, NOT) and sign extension
204     // could also be handled in the future.
205     for (Value *V : Defs)
206       if (!isa<PHINode>(V) && !isa<Constant>(V) && !isa<Argument>(V))
207         return false;
208 
209     for (Value *V : Defs)
210       if (const PHINode *P = dyn_cast<PHINode>(V))
211         if (!PromotablePHINodes.count(P))
212           return false;
213 
214     if (isa<ReturnInst>(U.getUser()))
215       ++NumBoolRetPromotion;
216     if (isa<CallInst>(U.getUser()))
217       ++NumBoolCallPromotion;
218     ++NumBoolToIntPromotion;
219 
220     for (Value *V : Defs)
221       if (!BoolToIntMap.count(V))
222         BoolToIntMap[V] = translate(V);
223 
224     // Replace the operands of the translated instructions. There were set to
225     // zero in the translate function.
226     for (auto &Pair : BoolToIntMap) {
227       User *First = dyn_cast<User>(Pair.first);
228       User *Second = dyn_cast<User>(Pair.second);
229       assert((!First || Second) && "translated from user to non-user!?");
230       if (First)
231         for (unsigned i = 0; i < First->getNumOperands(); ++i)
232           Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
233     }
234 
235     Value *IntRetVal = BoolToIntMap[U];
236     Type *Int1Ty = Type::getInt1Ty(U->getContext());
237     Instruction *I = cast<Instruction>(U.getUser());
238     Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
239     U.set(BackToBool);
240 
241     return true;
242   }
243 
getAnalysisUsage(AnalysisUsage & AU) const244   void getAnalysisUsage(AnalysisUsage &AU) const {
245     AU.addPreserved<DominatorTreeWrapperPass>();
246     FunctionPass::getAnalysisUsage(AU);
247   }
248 };
249 }
250 
251 char PPCBoolRetToInt::ID = 0;
252 INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
253                 "Convert i1 constants to i32 if they are returned",
254                 false, false)
255 
createPPCBoolRetToIntPass()256 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
257