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(); } 254
