388 lines · cpp
1//===-- SystemZTDC.cpp - Utilize Test Data Class instruction --------------===//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 pass looks for instructions that can be replaced by a Test Data Class10// instruction, and replaces them when profitable.11//12// Roughly, the following rules are recognized:13//14// 1: fcmp pred X, 0 -> tdc X, mask15// 2: fcmp pred X, +-inf -> tdc X, mask16// 3: fcmp pred X, +-minnorm -> tdc X, mask17// 4: tdc (fabs X), mask -> tdc X, newmask18// 5: icmp slt (bitcast float X to int), 0 -> tdc X, mask [ie. signbit]19// 6: icmp sgt (bitcast float X to int), -1 -> tdc X, mask20// 7: icmp ne/eq (call @llvm.s390.tdc.*(X, mask)) -> tdc X, mask/~mask21// 8: and i1 (tdc X, M1), (tdc X, M2) -> tdc X, (M1 & M2)22// 9: or i1 (tdc X, M1), (tdc X, M2) -> tdc X, (M1 | M2)23// 10: xor i1 (tdc X, M1), (tdc X, M2) -> tdc X, (M1 ^ M2)24//25// The pass works in 4 steps:26//27// 1. All fcmp and icmp instructions in a function are checked for a match28// with rules 1-3 and 5-7. Their TDC equivalents are stored in29// the ConvertedInsts mapping. If the operand of a fcmp instruction is30// a fabs, it's also folded according to rule 4.31// 2. All and/or/xor i1 instructions whose both operands have been already32// mapped are mapped according to rules 8-10. LogicOpsWorklist is used33// as a queue of instructions to check.34// 3. All mapped instructions that are considered worthy of conversion (ie.35// replacing them will actually simplify the final code) are replaced36// with a call to the s390.tdc intrinsic.37// 4. All intermediate results of replaced instructions are removed if unused.38//39// Instructions that match rules 1-3 are considered unworthy of conversion40// on their own (since a comparison instruction is superior), but are mapped41// in the hopes of folding the result using rules 4 and 8-10 (likely removing42// the original comparison in the process).43//44//===----------------------------------------------------------------------===//45 46#include "SystemZ.h"47#include "SystemZSubtarget.h"48#include "llvm/ADT/MapVector.h"49#include "llvm/CodeGen/TargetPassConfig.h"50#include "llvm/IR/Constants.h"51#include "llvm/IR/IRBuilder.h"52#include "llvm/IR/InstIterator.h"53#include "llvm/IR/Instructions.h"54#include "llvm/IR/IntrinsicsS390.h"55#include "llvm/IR/LegacyPassManager.h"56#include "llvm/IR/Module.h"57#include "llvm/Target/TargetMachine.h"58#include <set>59 60using namespace llvm;61 62namespace {63 64class SystemZTDCPass : public FunctionPass {65public:66 static char ID;67 SystemZTDCPass() : FunctionPass(ID) {}68 69 bool runOnFunction(Function &F) override;70 71 void getAnalysisUsage(AnalysisUsage &AU) const override {72 AU.addRequired<TargetPassConfig>();73 }74 75private:76 // Maps seen instructions that can be mapped to a TDC, values are77 // (TDC operand, TDC mask, worthy flag) triples.78 MapVector<Instruction *, std::tuple<Value *, int, bool>> ConvertedInsts;79 // The queue of and/or/xor i1 instructions to be potentially folded.80 std::vector<BinaryOperator *> LogicOpsWorklist;81 // Instructions matched while folding, to be removed at the end if unused.82 std::set<Instruction *> PossibleJunk;83 84 // Tries to convert a fcmp instruction.85 void convertFCmp(CmpInst &I);86 87 // Tries to convert an icmp instruction.88 void convertICmp(CmpInst &I);89 90 // Tries to convert an i1 and/or/xor instruction, whose both operands91 // have been already converted.92 void convertLogicOp(BinaryOperator &I);93 94 // Marks an instruction as converted - adds it to ConvertedInsts and adds95 // any and/or/xor i1 users to the queue.96 void converted(Instruction *I, Value *V, int Mask, bool Worthy) {97 ConvertedInsts[I] = std::make_tuple(V, Mask, Worthy);98 auto &M = *I->getFunction()->getParent();99 auto &Ctx = M.getContext();100 for (auto *U : I->users()) {101 auto *LI = dyn_cast<BinaryOperator>(U);102 if (LI && LI->getType() == Type::getInt1Ty(Ctx) &&103 (LI->getOpcode() == Instruction::And ||104 LI->getOpcode() == Instruction::Or ||105 LI->getOpcode() == Instruction::Xor)) {106 LogicOpsWorklist.push_back(LI);107 }108 }109 }110};111 112} // end anonymous namespace113 114char SystemZTDCPass::ID = 0;115INITIALIZE_PASS(SystemZTDCPass, "systemz-tdc",116 "SystemZ Test Data Class optimization", false, false)117 118FunctionPass *llvm::createSystemZTDCPass() {119 return new SystemZTDCPass();120}121 122void SystemZTDCPass::convertFCmp(CmpInst &I) {123 Value *Op0 = I.getOperand(0);124 auto *Const = dyn_cast<ConstantFP>(I.getOperand(1));125 auto Pred = I.getPredicate();126 // Only comparisons with consts are interesting.127 if (!Const)128 return;129 // Compute the smallest normal number (and its negation).130 auto &Sem = Op0->getType()->getFltSemantics();131 APFloat Smallest = APFloat::getSmallestNormalized(Sem);132 APFloat NegSmallest = Smallest;133 NegSmallest.changeSign();134 // Check if Const is one of our recognized consts.135 int WhichConst;136 if (Const->isZero()) {137 // All comparisons with 0 can be converted.138 WhichConst = 0;139 } else if (Const->isInfinity()) {140 // Likewise for infinities.141 WhichConst = Const->isNegative() ? 2 : 1;142 } else if (Const->isExactlyValue(Smallest)) {143 // For Smallest, we cannot do EQ separately from GT.144 if ((Pred & CmpInst::FCMP_OGE) != CmpInst::FCMP_OGE &&145 (Pred & CmpInst::FCMP_OGE) != 0)146 return;147 WhichConst = 3;148 } else if (Const->isExactlyValue(NegSmallest)) {149 // Likewise for NegSmallest, we cannot do EQ separately from LT.150 if ((Pred & CmpInst::FCMP_OLE) != CmpInst::FCMP_OLE &&151 (Pred & CmpInst::FCMP_OLE) != 0)152 return;153 WhichConst = 4;154 } else {155 // Not one of our special constants.156 return;157 }158 // Partial masks to use for EQ, GT, LT, UN comparisons, respectively.159 static const int Masks[][4] = {160 { // 0161 SystemZ::TDCMASK_ZERO, // eq162 SystemZ::TDCMASK_POSITIVE, // gt163 SystemZ::TDCMASK_NEGATIVE, // lt164 SystemZ::TDCMASK_NAN, // un165 },166 { // inf167 SystemZ::TDCMASK_INFINITY_PLUS, // eq168 0, // gt169 (SystemZ::TDCMASK_ZERO |170 SystemZ::TDCMASK_NEGATIVE |171 SystemZ::TDCMASK_NORMAL_PLUS |172 SystemZ::TDCMASK_SUBNORMAL_PLUS), // lt173 SystemZ::TDCMASK_NAN, // un174 },175 { // -inf176 SystemZ::TDCMASK_INFINITY_MINUS, // eq177 (SystemZ::TDCMASK_ZERO |178 SystemZ::TDCMASK_POSITIVE |179 SystemZ::TDCMASK_NORMAL_MINUS |180 SystemZ::TDCMASK_SUBNORMAL_MINUS), // gt181 0, // lt182 SystemZ::TDCMASK_NAN, // un183 },184 { // minnorm185 0, // eq (unsupported)186 (SystemZ::TDCMASK_NORMAL_PLUS |187 SystemZ::TDCMASK_INFINITY_PLUS), // gt (actually ge)188 (SystemZ::TDCMASK_ZERO |189 SystemZ::TDCMASK_NEGATIVE |190 SystemZ::TDCMASK_SUBNORMAL_PLUS), // lt191 SystemZ::TDCMASK_NAN, // un192 },193 { // -minnorm194 0, // eq (unsupported)195 (SystemZ::TDCMASK_ZERO |196 SystemZ::TDCMASK_POSITIVE |197 SystemZ::TDCMASK_SUBNORMAL_MINUS), // gt198 (SystemZ::TDCMASK_NORMAL_MINUS |199 SystemZ::TDCMASK_INFINITY_MINUS), // lt (actually le)200 SystemZ::TDCMASK_NAN, // un201 }202 };203 // Construct the mask as a combination of the partial masks.204 int Mask = 0;205 if (Pred & CmpInst::FCMP_OEQ)206 Mask |= Masks[WhichConst][0];207 if (Pred & CmpInst::FCMP_OGT)208 Mask |= Masks[WhichConst][1];209 if (Pred & CmpInst::FCMP_OLT)210 Mask |= Masks[WhichConst][2];211 if (Pred & CmpInst::FCMP_UNO)212 Mask |= Masks[WhichConst][3];213 // A lone fcmp is unworthy of tdc conversion on its own, but may become214 // worthy if combined with fabs.215 bool Worthy = false;216 if (CallInst *CI = dyn_cast<CallInst>(Op0)) {217 Function *F = CI->getCalledFunction();218 if (F && F->getIntrinsicID() == Intrinsic::fabs) {219 // Fold with fabs - adjust the mask appropriately.220 Mask &= SystemZ::TDCMASK_PLUS;221 Mask |= Mask >> 1;222 Op0 = CI->getArgOperand(0);223 // A combination of fcmp with fabs is a win, unless the constant224 // involved is 0 (which is handled by later passes).225 Worthy = WhichConst != 0;226 PossibleJunk.insert(CI);227 }228 }229 converted(&I, Op0, Mask, Worthy);230}231 232void SystemZTDCPass::convertICmp(CmpInst &I) {233 Value *Op0 = I.getOperand(0);234 auto *Const = dyn_cast<ConstantInt>(I.getOperand(1));235 auto Pred = I.getPredicate();236 // All our icmp rules involve comparisons with consts.237 if (!Const)238 return;239 if (auto *Cast = dyn_cast<BitCastInst>(Op0)) {240 // Check for icmp+bitcast used for signbit.241 if (!Cast->getSrcTy()->isFloatTy() &&242 !Cast->getSrcTy()->isDoubleTy() &&243 !Cast->getSrcTy()->isFP128Ty())244 return;245 Value *V = Cast->getOperand(0);246 int Mask;247 if (Pred == CmpInst::ICMP_SLT && Const->isZero()) {248 // icmp slt (bitcast X), 0 - set if sign bit true249 Mask = SystemZ::TDCMASK_MINUS;250 } else if (Pred == CmpInst::ICMP_SGT && Const->isMinusOne()) {251 // icmp sgt (bitcast X), -1 - set if sign bit false252 Mask = SystemZ::TDCMASK_PLUS;253 } else {254 // Not a sign bit check.255 return;256 }257 PossibleJunk.insert(Cast);258 converted(&I, V, Mask, true);259 } else if (auto *CI = dyn_cast<CallInst>(Op0)) {260 // Check if this is a pre-existing call of our tdc intrinsic.261 Function *F = CI->getCalledFunction();262 if (!F || F->getIntrinsicID() != Intrinsic::s390_tdc)263 return;264 if (!Const->isZero())265 return;266 Value *V = CI->getArgOperand(0);267 auto *MaskC = dyn_cast<ConstantInt>(CI->getArgOperand(1));268 // Bail if the mask is not a constant.269 if (!MaskC)270 return;271 int Mask = MaskC->getZExtValue();272 Mask &= SystemZ::TDCMASK_ALL;273 if (Pred == CmpInst::ICMP_NE) {274 // icmp ne (call llvm.s390.tdc(...)), 0 -> simple TDC275 } else if (Pred == CmpInst::ICMP_EQ) {276 // icmp eq (call llvm.s390.tdc(...)), 0 -> TDC with inverted mask277 Mask ^= SystemZ::TDCMASK_ALL;278 } else {279 // An unknown comparison - ignore.280 return;281 }282 PossibleJunk.insert(CI);283 converted(&I, V, Mask, false);284 }285}286 287void SystemZTDCPass::convertLogicOp(BinaryOperator &I) {288 Value *Op0, *Op1;289 int Mask0, Mask1;290 bool Worthy0, Worthy1;291 std::tie(Op0, Mask0, Worthy0) = ConvertedInsts[cast<Instruction>(I.getOperand(0))];292 std::tie(Op1, Mask1, Worthy1) = ConvertedInsts[cast<Instruction>(I.getOperand(1))];293 if (Op0 != Op1)294 return;295 int Mask;296 switch (I.getOpcode()) {297 case Instruction::And:298 Mask = Mask0 & Mask1;299 break;300 case Instruction::Or:301 Mask = Mask0 | Mask1;302 break;303 case Instruction::Xor:304 Mask = Mask0 ^ Mask1;305 break;306 default:307 llvm_unreachable("Unknown op in convertLogicOp");308 }309 converted(&I, Op0, Mask, true);310}311 312bool SystemZTDCPass::runOnFunction(Function &F) {313 auto &TPC = getAnalysis<TargetPassConfig>();314 if (TPC.getTM<TargetMachine>()315 .getSubtarget<SystemZSubtarget>(F)316 .hasSoftFloat())317 return false;318 319 ConvertedInsts.clear();320 LogicOpsWorklist.clear();321 PossibleJunk.clear();322 323 // Look for icmp+fcmp instructions.324 for (auto &I : instructions(F)) {325 if (I.getOpcode() == Instruction::FCmp)326 convertFCmp(cast<CmpInst>(I));327 else if (I.getOpcode() == Instruction::ICmp)328 convertICmp(cast<CmpInst>(I));329 }330 331 // If none found, bail already.332 if (ConvertedInsts.empty())333 return false;334 335 // Process the queue of logic instructions.336 while (!LogicOpsWorklist.empty()) {337 BinaryOperator *Op = LogicOpsWorklist.back();338 LogicOpsWorklist.pop_back();339 // If both operands mapped, and the instruction itself not yet mapped,340 // convert it.341 if (ConvertedInsts.count(dyn_cast<Instruction>(Op->getOperand(0))) &&342 ConvertedInsts.count(dyn_cast<Instruction>(Op->getOperand(1))) &&343 !ConvertedInsts.count(Op))344 convertLogicOp(*Op);345 }346 347 // Time to actually replace the instructions. Do it in the reverse order348 // of finding them, since there's a good chance the earlier ones will be349 // unused (due to being folded into later ones).350 Module &M = *F.getParent();351 auto &Ctx = M.getContext();352 Value *Zero32 = ConstantInt::get(Type::getInt32Ty(Ctx), 0);353 bool MadeChange = false;354 for (auto &It : reverse(ConvertedInsts)) {355 Instruction *I = It.first;356 Value *V;357 int Mask;358 bool Worthy;359 std::tie(V, Mask, Worthy) = It.second;360 if (!I->user_empty()) {361 // If used and unworthy of conversion, skip it.362 if (!Worthy)363 continue;364 // Call the intrinsic, compare result with 0.365 IRBuilder<> IRB(I);366 Value *MaskVal = ConstantInt::get(Type::getInt64Ty(Ctx), Mask);367 Instruction *TDC =368 IRB.CreateIntrinsic(Intrinsic::s390_tdc, V->getType(), {V, MaskVal});369 Value *ICmp = IRB.CreateICmp(CmpInst::ICMP_NE, TDC, Zero32);370 I->replaceAllUsesWith(ICmp);371 }372 // If unused, or used and converted, remove it.373 I->eraseFromParent();374 MadeChange = true;375 }376 377 if (!MadeChange)378 return false;379 380 // We've actually done something - now clear misc accumulated junk (fabs,381 // bitcast).382 for (auto *I : PossibleJunk)383 if (I->user_empty())384 I->eraseFromParent();385 386 return true;387}388