lib/Target/PowerPC/PPCBoolRetToInt.cpp

   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
  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
 248 char PPCBoolRetToInt::ID = 0;
 249 INITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int",
 250                 "Convert i1 constants to i32 if they are returned",
 251                 false, false)
 252
 253 FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }