1314564Sdim//===- PPCBoolRetToInt.cpp ------------------------------------------------===// 2292915Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6292915Sdim// 7292915Sdim//===----------------------------------------------------------------------===// 8292915Sdim// 9321369Sdim// This file implements converting i1 values to i32/i64 if they could be more 10292915Sdim// profitably allocated as GPRs rather than CRs. This pass will become totally 11292915Sdim// unnecessary if Register Bank Allocation and Global Instruction Selection ever 12292915Sdim// go upstream. 13292915Sdim// 14321369Sdim// Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the 15292915Sdim// transitive closure of their uses includes only PHINodes, CallInsts, and 16292915Sdim// ReturnInsts. The rational is that arguments are generally passed and returned 17321369Sdim// in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will 18292915Sdim// actually save casts at the Machine Instruction level. 19292915Sdim// 20292915Sdim// It might be useful to expand this pass to add bit-wise operations to the list 21292915Sdim// of safe transitive closure types. Also, we miss some opportunities when LLVM 22292915Sdim// represents logical AND and OR operations with control flow rather than data 23292915Sdim// flow. For example by lowering the expression: return (A && B && C) 24292915Sdim// 25292915Sdim// as: return A ? true : B && C. 26292915Sdim// 27292915Sdim// There's code in SimplifyCFG that code be used to turn control flow in data 28292915Sdim// flow using SelectInsts. Selects are slow on some architectures (P7/P8), so 29292915Sdim// this probably isn't good in general, but for the special case of i1, the 30292915Sdim// Selects could be further lowered to bit operations that are fast everywhere. 31292915Sdim// 32292915Sdim//===----------------------------------------------------------------------===// 33292915Sdim 34292915Sdim#include "PPC.h" 35321369Sdim#include "PPCTargetMachine.h" 36314564Sdim#include "llvm/ADT/DenseMap.h" 37321369Sdim#include "llvm/ADT/STLExtras.h" 38292915Sdim#include "llvm/ADT/SmallPtrSet.h" 39314564Sdim#include "llvm/ADT/SmallVector.h" 40292915Sdim#include "llvm/ADT/Statistic.h" 41314564Sdim#include "llvm/IR/Argument.h" 42292915Sdim#include "llvm/IR/Constants.h" 43292915Sdim#include "llvm/IR/Dominators.h" 44314564Sdim#include "llvm/IR/Function.h" 45314564Sdim#include "llvm/IR/Instruction.h" 46292915Sdim#include "llvm/IR/Instructions.h" 47292915Sdim#include "llvm/IR/IntrinsicInst.h" 48314564Sdim#include "llvm/IR/OperandTraits.h" 49314564Sdim#include "llvm/IR/Type.h" 50314564Sdim#include "llvm/IR/Use.h" 51314564Sdim#include "llvm/IR/User.h" 52314564Sdim#include "llvm/IR/Value.h" 53321369Sdim#include "llvm/Pass.h" 54321369Sdim#include "llvm/CodeGen/TargetPassConfig.h" 55314564Sdim#include "llvm/Support/Casting.h" 56314564Sdim#include <cassert> 57292915Sdim 58292915Sdimusing namespace llvm; 59292915Sdim 60292915Sdimnamespace { 61292915Sdim 62292915Sdim#define DEBUG_TYPE "bool-ret-to-int" 63292915Sdim 64292915SdimSTATISTIC(NumBoolRetPromotion, 65292915Sdim "Number of times a bool feeding a RetInst was promoted to an int"); 66292915SdimSTATISTIC(NumBoolCallPromotion, 67292915Sdim "Number of times a bool feeding a CallInst was promoted to an int"); 68292915SdimSTATISTIC(NumBoolToIntPromotion, 69292915Sdim "Total number of times a bool was promoted to an int"); 70292915Sdim 71292915Sdimclass PPCBoolRetToInt : public FunctionPass { 72292915Sdim static SmallPtrSet<Value *, 8> findAllDefs(Value *V) { 73292915Sdim SmallPtrSet<Value *, 8> Defs; 74292915Sdim SmallVector<Value *, 8> WorkList; 75292915Sdim WorkList.push_back(V); 76292915Sdim Defs.insert(V); 77292915Sdim while (!WorkList.empty()) { 78292915Sdim Value *Curr = WorkList.back(); 79292915Sdim WorkList.pop_back(); 80314564Sdim auto *CurrUser = dyn_cast<User>(Curr); 81314564Sdim // Operands of CallInst are skipped because they may not be Bool type, 82314564Sdim // and their positions are defined by ABI. 83314564Sdim if (CurrUser && !isa<CallInst>(Curr)) 84292915Sdim for (auto &Op : CurrUser->operands()) 85292915Sdim if (Defs.insert(Op).second) 86292915Sdim WorkList.push_back(Op); 87292915Sdim } 88292915Sdim return Defs; 89292915Sdim } 90292915Sdim 91321369Sdim // Translate a i1 value to an equivalent i32/i64 value: 92321369Sdim Value *translate(Value *V) { 93321369Sdim Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext()) 94321369Sdim : Type::getInt32Ty(V->getContext()); 95321369Sdim 96314564Sdim if (auto *C = dyn_cast<Constant>(V)) 97321369Sdim return ConstantExpr::getZExt(C, IntTy); 98314564Sdim if (auto *P = dyn_cast<PHINode>(V)) { 99292915Sdim // Temporarily set the operands to 0. We'll fix this later in 100292915Sdim // runOnUse. 101321369Sdim Value *Zero = Constant::getNullValue(IntTy); 102292915Sdim PHINode *Q = 103321369Sdim PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P); 104292915Sdim for (unsigned i = 0; i < P->getNumOperands(); ++i) 105292915Sdim Q->addIncoming(Zero, P->getIncomingBlock(i)); 106292915Sdim return Q; 107292915Sdim } 108292915Sdim 109314564Sdim auto *A = dyn_cast<Argument>(V); 110314564Sdim auto *I = dyn_cast<Instruction>(V); 111292915Sdim assert((A || I) && "Unknown value type"); 112292915Sdim 113292915Sdim auto InstPt = 114292915Sdim A ? &*A->getParent()->getEntryBlock().begin() : I->getNextNode(); 115321369Sdim return new ZExtInst(V, IntTy, "", InstPt); 116292915Sdim } 117292915Sdim 118292915Sdim typedef SmallPtrSet<const PHINode *, 8> PHINodeSet; 119292915Sdim 120292915Sdim // A PHINode is Promotable if: 121292915Sdim // 1. Its type is i1 AND 122292915Sdim // 2. All of its uses are ReturnInt, CallInst, PHINode, or DbgInfoIntrinsic 123292915Sdim // AND 124292915Sdim // 3. All of its operands are Constant or Argument or 125292915Sdim // CallInst or PHINode AND 126292915Sdim // 4. All of its PHINode uses are Promotable AND 127292915Sdim // 5. All of its PHINode operands are Promotable 128292915Sdim static PHINodeSet getPromotablePHINodes(const Function &F) { 129292915Sdim PHINodeSet Promotable; 130292915Sdim // Condition 1 131292915Sdim for (auto &BB : F) 132292915Sdim for (auto &I : BB) 133314564Sdim if (const auto *P = dyn_cast<PHINode>(&I)) 134292915Sdim if (P->getType()->isIntegerTy(1)) 135292915Sdim Promotable.insert(P); 136292915Sdim 137292915Sdim SmallVector<const PHINode *, 8> ToRemove; 138309124Sdim for (const PHINode *P : Promotable) { 139292915Sdim // Condition 2 and 3 140292915Sdim auto IsValidUser = [] (const Value *V) -> bool { 141292915Sdim return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V) || 142292915Sdim isa<DbgInfoIntrinsic>(V); 143292915Sdim }; 144292915Sdim auto IsValidOperand = [] (const Value *V) -> bool { 145292915Sdim return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) || 146292915Sdim isa<PHINode>(V); 147292915Sdim }; 148292915Sdim const auto &Users = P->users(); 149292915Sdim const auto &Operands = P->operands(); 150314564Sdim if (!llvm::all_of(Users, IsValidUser) || 151314564Sdim !llvm::all_of(Operands, IsValidOperand)) 152292915Sdim ToRemove.push_back(P); 153292915Sdim } 154292915Sdim 155292915Sdim // Iterate to convergence 156292915Sdim auto IsPromotable = [&Promotable] (const Value *V) -> bool { 157314564Sdim const auto *Phi = dyn_cast<PHINode>(V); 158292915Sdim return !Phi || Promotable.count(Phi); 159292915Sdim }; 160292915Sdim while (!ToRemove.empty()) { 161292915Sdim for (auto &User : ToRemove) 162292915Sdim Promotable.erase(User); 163292915Sdim ToRemove.clear(); 164292915Sdim 165309124Sdim for (const PHINode *P : Promotable) { 166292915Sdim // Condition 4 and 5 167292915Sdim const auto &Users = P->users(); 168292915Sdim const auto &Operands = P->operands(); 169314564Sdim if (!llvm::all_of(Users, IsPromotable) || 170314564Sdim !llvm::all_of(Operands, IsPromotable)) 171292915Sdim ToRemove.push_back(P); 172292915Sdim } 173292915Sdim } 174292915Sdim 175292915Sdim return Promotable; 176292915Sdim } 177292915Sdim 178292915Sdim typedef DenseMap<Value *, Value *> B2IMap; 179292915Sdim 180292915Sdim public: 181292915Sdim static char ID; 182314564Sdim 183292915Sdim PPCBoolRetToInt() : FunctionPass(ID) { 184292915Sdim initializePPCBoolRetToIntPass(*PassRegistry::getPassRegistry()); 185292915Sdim } 186292915Sdim 187314564Sdim bool runOnFunction(Function &F) override { 188309124Sdim if (skipFunction(F)) 189309124Sdim return false; 190309124Sdim 191321369Sdim auto *TPC = getAnalysisIfAvailable<TargetPassConfig>(); 192321369Sdim if (!TPC) 193321369Sdim return false; 194321369Sdim 195321369Sdim auto &TM = TPC->getTM<PPCTargetMachine>(); 196321369Sdim ST = TM.getSubtargetImpl(F); 197321369Sdim 198292915Sdim PHINodeSet PromotablePHINodes = getPromotablePHINodes(F); 199292915Sdim B2IMap Bool2IntMap; 200292915Sdim bool Changed = false; 201292915Sdim for (auto &BB : F) { 202292915Sdim for (auto &I : BB) { 203314564Sdim if (auto *R = dyn_cast<ReturnInst>(&I)) 204292915Sdim if (F.getReturnType()->isIntegerTy(1)) 205292915Sdim Changed |= 206292915Sdim runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap); 207292915Sdim 208314564Sdim if (auto *CI = dyn_cast<CallInst>(&I)) 209292915Sdim for (auto &U : CI->operands()) 210292915Sdim if (U->getType()->isIntegerTy(1)) 211292915Sdim Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap); 212292915Sdim } 213292915Sdim } 214292915Sdim 215292915Sdim return Changed; 216292915Sdim } 217292915Sdim 218321369Sdim bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes, 219292915Sdim B2IMap &BoolToIntMap) { 220292915Sdim auto Defs = findAllDefs(U); 221292915Sdim 222292915Sdim // If the values are all Constants or Arguments, don't bother 223314564Sdim if (llvm::none_of(Defs, isa<Instruction, Value *>)) 224292915Sdim return false; 225292915Sdim 226314564Sdim // Presently, we only know how to handle PHINode, Constant, Arguments and 227314564Sdim // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign 228314564Sdim // extension could also be handled in the future. 229309124Sdim for (Value *V : Defs) 230314564Sdim if (!isa<PHINode>(V) && !isa<Constant>(V) && 231314564Sdim !isa<Argument>(V) && !isa<CallInst>(V)) 232292915Sdim return false; 233292915Sdim 234309124Sdim for (Value *V : Defs) 235314564Sdim if (const auto *P = dyn_cast<PHINode>(V)) 236292915Sdim if (!PromotablePHINodes.count(P)) 237292915Sdim return false; 238292915Sdim 239292915Sdim if (isa<ReturnInst>(U.getUser())) 240292915Sdim ++NumBoolRetPromotion; 241292915Sdim if (isa<CallInst>(U.getUser())) 242292915Sdim ++NumBoolCallPromotion; 243292915Sdim ++NumBoolToIntPromotion; 244292915Sdim 245309124Sdim for (Value *V : Defs) 246292915Sdim if (!BoolToIntMap.count(V)) 247292915Sdim BoolToIntMap[V] = translate(V); 248292915Sdim 249314564Sdim // Replace the operands of the translated instructions. They were set to 250292915Sdim // zero in the translate function. 251292915Sdim for (auto &Pair : BoolToIntMap) { 252314564Sdim auto *First = dyn_cast<User>(Pair.first); 253314564Sdim auto *Second = dyn_cast<User>(Pair.second); 254292915Sdim assert((!First || Second) && "translated from user to non-user!?"); 255314564Sdim // Operands of CallInst are skipped because they may not be Bool type, 256314564Sdim // and their positions are defined by ABI. 257314564Sdim if (First && !isa<CallInst>(First)) 258292915Sdim for (unsigned i = 0; i < First->getNumOperands(); ++i) 259292915Sdim Second->setOperand(i, BoolToIntMap[First->getOperand(i)]); 260292915Sdim } 261292915Sdim 262292915Sdim Value *IntRetVal = BoolToIntMap[U]; 263292915Sdim Type *Int1Ty = Type::getInt1Ty(U->getContext()); 264314564Sdim auto *I = cast<Instruction>(U.getUser()); 265292915Sdim Value *BackToBool = new TruncInst(IntRetVal, Int1Ty, "backToBool", I); 266292915Sdim U.set(BackToBool); 267292915Sdim 268292915Sdim return true; 269292915Sdim } 270292915Sdim 271314564Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 272292915Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 273292915Sdim FunctionPass::getAnalysisUsage(AU); 274292915Sdim } 275321369Sdim 276321369Sdimprivate: 277321369Sdim const PPCSubtarget *ST; 278292915Sdim}; 279292915Sdim 280314564Sdim} // end anonymous namespace 281314564Sdim 282292915Sdimchar PPCBoolRetToInt::ID = 0; 283292915SdimINITIALIZE_PASS(PPCBoolRetToInt, "bool-ret-to-int", 284321369Sdim "Convert i1 constants to i32/i64 if they are returned", 285292915Sdim false, false) 286292915Sdim 287292915SdimFunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); } 288