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
46using namespace llvm;
47
48namespace {
49
50#define DEBUG_TYPE "bool-ret-to-int"
51
52STATISTIC(NumBoolRetPromotion,
53          "Number of times a bool feeding a RetInst was promoted to an int");
54STATISTIC(NumBoolCallPromotion,
55          "Number of times a bool feeding a CallInst was promoted to an int");
56STATISTIC(NumBoolToIntPromotion,
57          "Total number of times a bool was promoted to an int");
58
59class PPCBoolRetToInt : public FunctionPass {
60
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:
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
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 auto &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 auto &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;
166  PPCBoolRetToInt() : FunctionPass(ID) {
167    initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry());
168  }
169
170  bool runOnFunction(Function &F) {
171    PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);
172    B2IMap Bool2IntMap;
173    bool Changed = false;
174    for (auto &BB : F) {
175      for (auto &I : BB) {
176        if (ReturnInst *R = dyn_cast<ReturnInst>(&I))
177          if (F.getReturnType()->isIntegerTy(1))
178            Changed |=
179              runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);
180
181        if (CallInst *CI = dyn_cast<CallInst>(&I))
182          for (auto &U : CI->operands())
183            if (U->getType()->isIntegerTy(1))
184              Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);
185      }
186    }
187
188    return Changed;
189  }
190
191  static bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,
192                       B2IMap &BoolToIntMap) {
193    auto Defs = findAllDefs(U);
194
195    // If the values are all Constants or Arguments, don't bother
196    if (!std::any_of(Defs.begin(), Defs.end(), isa<Instruction, Value *>))
197      return false;
198
199    // Presently, we only know how to handle PHINode, Constant, and Arguments.
200    // Potentially, bitwise operations (AND, OR, XOR, NOT) and sign extension
201    // could also be handled in the future.
202    for (const auto &V : Defs)
203      if (!isa<PHINode>(V) && !isa<Constant>(V) && !isa<Argument>(V))
204        return false;
205
206    for (const auto &V : Defs)
207      if (const PHINode *P = dyn_cast<PHINode>(V))
208        if (!PromotablePHINodes.count(P))
209          return false;
210
211    if (isa<ReturnInst>(U.getUser()))
212      ++NumBoolRetPromotion;
213    if (isa<CallInst>(U.getUser()))
214      ++NumBoolCallPromotion;
215    ++NumBoolToIntPromotion;
216
217    for (const auto &V : Defs)
218      if (!BoolToIntMap.count(V))
219        BoolToIntMap[V] = translate(V);
220
221    // Replace the operands of the translated instructions. There were set to
222    // zero in the translate function.
223    for (auto &Pair : BoolToIntMap) {
224      User *First = dyn_cast<User>(Pair.first);
225      User *Second = dyn_cast<User>(Pair.second);
226      assert((!First || Second) && "translated from user to non-user!?");
227      if (First)
228        for (unsigned i = 0; i < First->getNumOperands(); ++i)
229          Second->setOperand(i, BoolToIntMap[First->getOperand(i)]);
230    }
231
232    Value *IntRetVal = BoolToIntMap[U];
233    Type *Int1Ty = Type::getInt1Ty(U->getContext());
234    Instruction *I = cast<Instruction>(U.getUser());
235    Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I);
236    U.set(BackToBool);
237
238    return true;
239  }
240
241  void getAnalysisUsage(AnalysisUsage &AU) const {
242    AU.addPreserved<DominatorTreeWrapperPass>();
243    FunctionPass::getAnalysisUsage(AU);
244  }
245};
246}
247
248char PPCBoolRetToInt::ID = 0;
249INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
250                "Convert i1 constants to i32 if they are returned",
251                false, false)
252
253FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }
254