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