287 lines · cpp
1//===- PPCBoolRetToInt.cpp ------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements converting i1 values to i32/i64 if they could be more10// profitably allocated as GPRs rather than CRs. This pass will become totally11// unnecessary if Register Bank Allocation and Global Instruction Selection ever12// go upstream.13//14// Presently, the pass converts i1 Constants, and Arguments to i32/i64 if the15// transitive closure of their uses includes only PHINodes, CallInsts, and16// ReturnInsts. The rational is that arguments are generally passed and returned17// in GPRs rather than CRs, so casting them to i32/i64 at the LLVM IR level will18// actually save casts at the Machine Instruction level.19//20// It might be useful to expand this pass to add bit-wise operations to the list21// of safe transitive closure types. Also, we miss some opportunities when LLVM22// represents logical AND and OR operations with control flow rather than data23// flow. For example by lowering the expression: return (A && B && C)24//25// as: return A ? true : B && C.26//27// There's code in SimplifyCFG that code be used to turn control flow in data28// flow using SelectInsts. Selects are slow on some architectures (P7/P8), so29// this probably isn't good in general, but for the special case of i1, the30// Selects could be further lowered to bit operations that are fast everywhere.31//32//===----------------------------------------------------------------------===//33 34#include "PPC.h"35#include "PPCTargetMachine.h"36#include "llvm/ADT/DenseMap.h"37#include "llvm/ADT/STLExtras.h"38#include "llvm/ADT/SmallPtrSet.h"39#include "llvm/ADT/SmallVector.h"40#include "llvm/ADT/Statistic.h"41#include "llvm/CodeGen/TargetPassConfig.h"42#include "llvm/IR/Argument.h"43#include "llvm/IR/Dominators.h"44#include "llvm/IR/Function.h"45#include "llvm/IR/IRBuilder.h"46#include "llvm/IR/Instruction.h"47#include "llvm/IR/Instructions.h"48#include "llvm/IR/Type.h"49#include "llvm/IR/Use.h"50#include "llvm/IR/User.h"51#include "llvm/IR/Value.h"52#include "llvm/Pass.h"53#include "llvm/Support/Casting.h"54#include <cassert>55 56using namespace llvm;57 58namespace {59 60#define DEBUG_TYPE "ppc-bool-ret-to-int"61 62STATISTIC(NumBoolRetPromotion,63 "Number of times a bool feeding a RetInst was promoted to an int");64STATISTIC(NumBoolCallPromotion,65 "Number of times a bool feeding a CallInst was promoted to an int");66STATISTIC(NumBoolToIntPromotion,67 "Total number of times a bool was promoted to an int");68 69class PPCBoolRetToInt : public FunctionPass {70 static SmallPtrSet<Value *, 8> findAllDefs(Value *V) {71 SmallPtrSet<Value *, 8> Defs;72 SmallVector<Value *, 8> WorkList;73 WorkList.push_back(V);74 Defs.insert(V);75 while (!WorkList.empty()) {76 Value *Curr = WorkList.pop_back_val();77 auto *CurrUser = dyn_cast<User>(Curr);78 // Operands of CallInst/Constant are skipped because they may not be Bool79 // type. For CallInst, their positions are defined by ABI.80 if (CurrUser && !isa<CallInst>(Curr) && !isa<Constant>(Curr))81 for (auto &Op : CurrUser->operands())82 if (Defs.insert(Op).second)83 WorkList.push_back(Op);84 }85 return Defs;86 }87 88 // Translate a i1 value to an equivalent i32/i64 value:89 Value *translate(Value *V) {90 assert(V->getType() == Type::getInt1Ty(V->getContext()) &&91 "Expect an i1 value");92 93 Type *IntTy = ST->isPPC64() ? Type::getInt64Ty(V->getContext())94 : Type::getInt32Ty(V->getContext());95 96 if (auto *P = dyn_cast<PHINode>(V)) {97 // Temporarily set the operands to 0. We'll fix this later in98 // runOnUse.99 Value *Zero = Constant::getNullValue(IntTy);100 PHINode *Q =101 PHINode::Create(IntTy, P->getNumIncomingValues(), P->getName(), P->getIterator());102 for (unsigned I = 0; I < P->getNumOperands(); ++I)103 Q->addIncoming(Zero, P->getIncomingBlock(I));104 return Q;105 }106 107 IRBuilder IRB(V->getContext());108 if (auto *I = dyn_cast<Instruction>(V))109 IRB.SetInsertPoint(I->getNextNode());110 else111 IRB.SetInsertPoint(&Func->getEntryBlock(), Func->getEntryBlock().begin());112 return IRB.CreateZExt(V, IntTy);113 }114 115 typedef SmallPtrSet<const PHINode *, 8> PHINodeSet;116 117 // A PHINode is Promotable if:118 // 1. Its type is i1 AND119 // 2. All of its uses are ReturnInt, CallInst, or PHINode120 // AND121 // 3. All of its operands are Constant or Argument or122 // CallInst or PHINode AND123 // 4. All of its PHINode uses are Promotable AND124 // 5. All of its PHINode operands are Promotable125 static PHINodeSet getPromotablePHINodes(const Function &F) {126 PHINodeSet Promotable;127 // Condition 1128 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 3137 auto IsValidUser = [] (const Value *V) -> bool {138 return isa<ReturnInst>(V) || isa<CallInst>(V) || isa<PHINode>(V);139 };140 auto IsValidOperand = [] (const Value *V) -> bool {141 return isa<Constant>(V) || isa<Argument>(V) || isa<CallInst>(V) ||142 isa<PHINode>(V);143 };144 const auto &Users = P->users();145 const auto &Operands = P->operands();146 if (!llvm::all_of(Users, IsValidUser) ||147 !llvm::all_of(Operands, IsValidOperand))148 ToRemove.push_back(P);149 }150 151 // Iterate to convergence152 auto IsPromotable = [&Promotable] (const Value *V) -> bool {153 const auto *Phi = dyn_cast<PHINode>(V);154 return !Phi || Promotable.count(Phi);155 };156 while (!ToRemove.empty()) {157 for (auto &User : ToRemove)158 Promotable.erase(User);159 ToRemove.clear();160 161 for (const PHINode *P : Promotable) {162 // Condition 4 and 5163 const auto &Users = P->users();164 const auto &Operands = P->operands();165 if (!llvm::all_of(Users, IsPromotable) ||166 !llvm::all_of(Operands, IsPromotable))167 ToRemove.push_back(P);168 }169 }170 171 return Promotable;172 }173 174 typedef DenseMap<Value *, Value *> B2IMap;175 176 public:177 static char ID;178 179 PPCBoolRetToInt() : FunctionPass(ID) {}180 181 bool runOnFunction(Function &F) override {182 if (skipFunction(F))183 return false;184 185 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();186 if (!TPC)187 return false;188 189 auto &TM = TPC->getTM<PPCTargetMachine>();190 ST = TM.getSubtargetImpl(F);191 Func = &F;192 193 PHINodeSet PromotablePHINodes = getPromotablePHINodes(F);194 B2IMap Bool2IntMap;195 bool Changed = false;196 for (auto &BB : F) {197 for (auto &I : BB) {198 if (auto *R = dyn_cast<ReturnInst>(&I))199 if (F.getReturnType()->isIntegerTy(1))200 Changed |=201 runOnUse(R->getOperandUse(0), PromotablePHINodes, Bool2IntMap);202 203 if (auto *CI = dyn_cast<CallInst>(&I))204 for (auto &U : CI->operands())205 if (U->getType()->isIntegerTy(1))206 Changed |= runOnUse(U, PromotablePHINodes, Bool2IntMap);207 }208 }209 210 return Changed;211 }212 213 bool runOnUse(Use &U, const PHINodeSet &PromotablePHINodes,214 B2IMap &BoolToIntMap) {215 auto Defs = findAllDefs(U);216 217 // If the values are all Constants or Arguments, don't bother218 if (llvm::none_of(Defs, [](Value *V) { return isa<Instruction>(V); }))219 return false;220 221 // Presently, we only know how to handle PHINode, Constant, Arguments and222 // CallInst. Potentially, bitwise operations (AND, OR, XOR, NOT) and sign223 // extension could also be handled in the future.224 for (Value *V : Defs)225 if (!isa<PHINode>(V) && !isa<Constant>(V) &&226 !isa<Argument>(V) && !isa<CallInst>(V))227 return false;228 229 for (Value *V : Defs)230 if (const auto *P = dyn_cast<PHINode>(V))231 if (!PromotablePHINodes.count(P))232 return false;233 234 if (isa<ReturnInst>(U.getUser()))235 ++NumBoolRetPromotion;236 if (isa<CallInst>(U.getUser()))237 ++NumBoolCallPromotion;238 ++NumBoolToIntPromotion;239 240 for (Value *V : Defs) {241 auto [It, Inserted] = BoolToIntMap.try_emplace(V);242 if (Inserted)243 It->second = translate(V);244 }245 246 // Replace the operands of the translated instructions. They were set to247 // zero in the translate function.248 for (auto &Pair : BoolToIntMap) {249 auto *First = dyn_cast<User>(Pair.first);250 auto *Second = dyn_cast<User>(Pair.second);251 assert((!First || Second) && "translated from user to non-user!?");252 // Operands of CallInst/Constant are skipped because they may not be Bool253 // type. For CallInst, their positions are defined by ABI.254 if (First && !isa<CallInst>(First) && !isa<Constant>(First))255 for (unsigned I = 0; I < First->getNumOperands(); ++I)256 Second->setOperand(I, BoolToIntMap[First->getOperand(I)]);257 }258 259 Value *IntRetVal = BoolToIntMap[U];260 Type *Int1Ty = Type::getInt1Ty(U->getContext());261 auto *I = cast<Instruction>(U.getUser());262 Value *BackToBool =263 new TruncInst(IntRetVal, Int1Ty, "backToBool", I->getIterator());264 U.set(BackToBool);265 266 return true;267 }268 269 void getAnalysisUsage(AnalysisUsage &AU) const override {270 AU.addPreserved<DominatorTreeWrapperPass>();271 FunctionPass::getAnalysisUsage(AU);272 }273 274private:275 const PPCSubtarget *ST;276 Function *Func;277};278 279} // end anonymous namespace280 281char PPCBoolRetToInt::ID = 0;282INITIALIZE_PASS(PPCBoolRetToInt, "ppc-bool-ret-to-int",283 "Convert i1 constants to i32/i64 if they are returned", false,284 false)285 286FunctionPass *llvm::createPPCBoolRetToIntPass() { return new PPCBoolRetToInt(); }287