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