1 //===-- LoopUtils.cpp - Loop Utility functions -------------------------===// 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 defines common loop utility functions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/LoopInfo.h" 15 #include "llvm/IR/Instructions.h" 16 #include "llvm/IR/PatternMatch.h" 17 #include "llvm/IR/ValueHandle.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Transforms/Utils/LoopUtils.h" 20 21 using namespace llvm; 22 using namespace llvm::PatternMatch; 23 24 #define DEBUG_TYPE "loop-utils" 25 26 bool ReductionDescriptor::areAllUsesIn(Instruction *I, 27 SmallPtrSetImpl<Instruction *> &Set) { 28 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) 29 if (!Set.count(dyn_cast<Instruction>(*Use))) 30 return false; 31 return true; 32 } 33 34 bool ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, 35 Loop *TheLoop, bool HasFunNoNaNAttr, 36 ReductionDescriptor &RedDes) { 37 if (Phi->getNumIncomingValues() != 2) 38 return false; 39 40 // Reduction variables are only found in the loop header block. 41 if (Phi->getParent() != TheLoop->getHeader()) 42 return false; 43 44 // Obtain the reduction start value from the value that comes from the loop 45 // preheader. 46 Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); 47 48 // ExitInstruction is the single value which is used outside the loop. 49 // We only allow for a single reduction value to be used outside the loop. 50 // This includes users of the reduction, variables (which form a cycle 51 // which ends in the phi node). 52 Instruction *ExitInstruction = nullptr; 53 // Indicates that we found a reduction operation in our scan. 54 bool FoundReduxOp = false; 55 56 // We start with the PHI node and scan for all of the users of this 57 // instruction. All users must be instructions that can be used as reduction 58 // variables (such as ADD). We must have a single out-of-block user. The cycle 59 // must include the original PHI. 60 bool FoundStartPHI = false; 61 62 // To recognize min/max patterns formed by a icmp select sequence, we store 63 // the number of instruction we saw from the recognized min/max pattern, 64 // to make sure we only see exactly the two instructions. 65 unsigned NumCmpSelectPatternInst = 0; 66 ReductionInstDesc ReduxDesc(false, nullptr); 67 68 SmallPtrSet<Instruction *, 8> VisitedInsts; 69 SmallVector<Instruction *, 8> Worklist; 70 Worklist.push_back(Phi); 71 VisitedInsts.insert(Phi); 72 73 // A value in the reduction can be used: 74 // - By the reduction: 75 // - Reduction operation: 76 // - One use of reduction value (safe). 77 // - Multiple use of reduction value (not safe). 78 // - PHI: 79 // - All uses of the PHI must be the reduction (safe). 80 // - Otherwise, not safe. 81 // - By one instruction outside of the loop (safe). 82 // - By further instructions outside of the loop (not safe). 83 // - By an instruction that is not part of the reduction (not safe). 84 // This is either: 85 // * An instruction type other than PHI or the reduction operation. 86 // * A PHI in the header other than the initial PHI. 87 while (!Worklist.empty()) { 88 Instruction *Cur = Worklist.back(); 89 Worklist.pop_back(); 90 91 // No Users. 92 // If the instruction has no users then this is a broken chain and can't be 93 // a reduction variable. 94 if (Cur->use_empty()) 95 return false; 96 97 bool IsAPhi = isa<PHINode>(Cur); 98 99 // A header PHI use other than the original PHI. 100 if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) 101 return false; 102 103 // Reductions of instructions such as Div, and Sub is only possible if the 104 // LHS is the reduction variable. 105 if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) && 106 !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) && 107 !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))) 108 return false; 109 110 // Any reduction instruction must be of one of the allowed kinds. 111 ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); 112 if (!ReduxDesc.isReduction()) 113 return false; 114 115 // A reduction operation must only have one use of the reduction value. 116 if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax && 117 hasMultipleUsesOf(Cur, VisitedInsts)) 118 return false; 119 120 // All inputs to a PHI node must be a reduction value. 121 if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) 122 return false; 123 124 if (Kind == RK_IntegerMinMax && 125 (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur))) 126 ++NumCmpSelectPatternInst; 127 if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur))) 128 ++NumCmpSelectPatternInst; 129 130 // Check whether we found a reduction operator. 131 FoundReduxOp |= !IsAPhi; 132 133 // Process users of current instruction. Push non-PHI nodes after PHI nodes 134 // onto the stack. This way we are going to have seen all inputs to PHI 135 // nodes once we get to them. 136 SmallVector<Instruction *, 8> NonPHIs; 137 SmallVector<Instruction *, 8> PHIs; 138 for (User *U : Cur->users()) { 139 Instruction *UI = cast<Instruction>(U); 140 141 // Check if we found the exit user. 142 BasicBlock *Parent = UI->getParent(); 143 if (!TheLoop->contains(Parent)) { 144 // Exit if you find multiple outside users or if the header phi node is 145 // being used. In this case the user uses the value of the previous 146 // iteration, in which case we would loose "VF-1" iterations of the 147 // reduction operation if we vectorize. 148 if (ExitInstruction != nullptr || Cur == Phi) 149 return false; 150 151 // The instruction used by an outside user must be the last instruction 152 // before we feed back to the reduction phi. Otherwise, we loose VF-1 153 // operations on the value. 154 if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end()) 155 return false; 156 157 ExitInstruction = Cur; 158 continue; 159 } 160 161 // Process instructions only once (termination). Each reduction cycle 162 // value must only be used once, except by phi nodes and min/max 163 // reductions which are represented as a cmp followed by a select. 164 ReductionInstDesc IgnoredVal(false, nullptr); 165 if (VisitedInsts.insert(UI).second) { 166 if (isa<PHINode>(UI)) 167 PHIs.push_back(UI); 168 else 169 NonPHIs.push_back(UI); 170 } else if (!isa<PHINode>(UI) && 171 ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) && 172 !isa<SelectInst>(UI)) || 173 !isMinMaxSelectCmpPattern(UI, IgnoredVal).isReduction())) 174 return false; 175 176 // Remember that we completed the cycle. 177 if (UI == Phi) 178 FoundStartPHI = true; 179 } 180 Worklist.append(PHIs.begin(), PHIs.end()); 181 Worklist.append(NonPHIs.begin(), NonPHIs.end()); 182 } 183 184 // This means we have seen one but not the other instruction of the 185 // pattern or more than just a select and cmp. 186 if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && 187 NumCmpSelectPatternInst != 2) 188 return false; 189 190 if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) 191 return false; 192 193 // We found a reduction var if we have reached the original phi node and we 194 // only have a single instruction with out-of-loop users. 195 196 // The ExitInstruction(Instruction which is allowed to have out-of-loop users) 197 // is saved as part of the ReductionDescriptor. 198 199 // Save the description of this reduction variable. 200 ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, 201 ReduxDesc.getMinMaxKind()); 202 203 RedDes = RD; 204 205 return true; 206 } 207 208 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction 209 /// pattern corresponding to a min(X, Y) or max(X, Y). 210 ReductionInstDesc 211 ReductionDescriptor::isMinMaxSelectCmpPattern(Instruction *I, 212 ReductionInstDesc &Prev) { 213 214 assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) && 215 "Expect a select instruction"); 216 Instruction *Cmp = nullptr; 217 SelectInst *Select = nullptr; 218 219 // We must handle the select(cmp()) as a single instruction. Advance to the 220 // select. 221 if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) { 222 if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin()))) 223 return ReductionInstDesc(false, I); 224 return ReductionInstDesc(Select, Prev.getMinMaxKind()); 225 } 226 227 // Only handle single use cases for now. 228 if (!(Select = dyn_cast<SelectInst>(I))) 229 return ReductionInstDesc(false, I); 230 if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) && 231 !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0)))) 232 return ReductionInstDesc(false, I); 233 if (!Cmp->hasOneUse()) 234 return ReductionInstDesc(false, I); 235 236 Value *CmpLeft; 237 Value *CmpRight; 238 239 // Look for a min/max pattern. 240 if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 241 return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMin); 242 else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 243 return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMax); 244 else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 245 return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMax); 246 else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 247 return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMin); 248 else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 249 return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); 250 else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 251 return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); 252 else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 253 return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); 254 else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) 255 return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); 256 257 return ReductionInstDesc(false, I); 258 } 259 260 ReductionInstDesc ReductionDescriptor::isReductionInstr(Instruction *I, 261 ReductionKind Kind, 262 ReductionInstDesc &Prev, 263 bool HasFunNoNaNAttr) { 264 bool FP = I->getType()->isFloatingPointTy(); 265 bool FastMath = FP && I->hasUnsafeAlgebra(); 266 switch (I->getOpcode()) { 267 default: 268 return ReductionInstDesc(false, I); 269 case Instruction::PHI: 270 if (FP && 271 (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax)) 272 return ReductionInstDesc(false, I); 273 return ReductionInstDesc(I, Prev.getMinMaxKind()); 274 case Instruction::Sub: 275 case Instruction::Add: 276 return ReductionInstDesc(Kind == RK_IntegerAdd, I); 277 case Instruction::Mul: 278 return ReductionInstDesc(Kind == RK_IntegerMult, I); 279 case Instruction::And: 280 return ReductionInstDesc(Kind == RK_IntegerAnd, I); 281 case Instruction::Or: 282 return ReductionInstDesc(Kind == RK_IntegerOr, I); 283 case Instruction::Xor: 284 return ReductionInstDesc(Kind == RK_IntegerXor, I); 285 case Instruction::FMul: 286 return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I); 287 case Instruction::FSub: 288 case Instruction::FAdd: 289 return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I); 290 case Instruction::FCmp: 291 case Instruction::ICmp: 292 case Instruction::Select: 293 if (Kind != RK_IntegerMinMax && 294 (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) 295 return ReductionInstDesc(false, I); 296 return isMinMaxSelectCmpPattern(I, Prev); 297 } 298 } 299 300 bool ReductionDescriptor::hasMultipleUsesOf( 301 Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) { 302 unsigned NumUses = 0; 303 for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; 304 ++Use) { 305 if (Insts.count(dyn_cast<Instruction>(*Use))) 306 ++NumUses; 307 if (NumUses > 1) 308 return true; 309 } 310 311 return false; 312 } 313 bool ReductionDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop, 314 ReductionDescriptor &RedDes) { 315 316 bool HasFunNoNaNAttr = false; 317 BasicBlock *Header = TheLoop->getHeader(); 318 Function &F = *Header->getParent(); 319 if (F.hasFnAttribute("no-nans-fp-math")) 320 HasFunNoNaNAttr = 321 F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; 322 323 if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { 324 DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n"); 325 return true; 326 } 327 if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) { 328 DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); 329 return true; 330 } 331 if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) { 332 DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); 333 return true; 334 } 335 if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) { 336 DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); 337 return true; 338 } 339 if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) { 340 DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); 341 return true; 342 } 343 if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, 344 RedDes)) { 345 DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n"); 346 return true; 347 } 348 if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { 349 DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); 350 return true; 351 } 352 if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { 353 DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); 354 return true; 355 } 356 if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { 357 DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n"); 358 return true; 359 } 360 // Not a reduction of known type. 361 return false; 362 } 363 364 /// This function returns the identity element (or neutral element) for 365 /// the operation K. 366 Constant *ReductionDescriptor::getReductionIdentity(ReductionKind K, Type *Tp) { 367 switch (K) { 368 case RK_IntegerXor: 369 case RK_IntegerAdd: 370 case RK_IntegerOr: 371 // Adding, Xoring, Oring zero to a number does not change it. 372 return ConstantInt::get(Tp, 0); 373 case RK_IntegerMult: 374 // Multiplying a number by 1 does not change it. 375 return ConstantInt::get(Tp, 1); 376 case RK_IntegerAnd: 377 // AND-ing a number with an all-1 value does not change it. 378 return ConstantInt::get(Tp, -1, true); 379 case RK_FloatMult: 380 // Multiplying a number by 1 does not change it. 381 return ConstantFP::get(Tp, 1.0L); 382 case RK_FloatAdd: 383 // Adding zero to a number does not change it. 384 return ConstantFP::get(Tp, 0.0L); 385 default: 386 llvm_unreachable("Unknown reduction kind"); 387 } 388 } 389 390 /// This function translates the reduction kind to an LLVM binary operator. 391 unsigned ReductionDescriptor::getReductionBinOp(ReductionKind Kind) { 392 switch (Kind) { 393 case RK_IntegerAdd: 394 return Instruction::Add; 395 case RK_IntegerMult: 396 return Instruction::Mul; 397 case RK_IntegerOr: 398 return Instruction::Or; 399 case RK_IntegerAnd: 400 return Instruction::And; 401 case RK_IntegerXor: 402 return Instruction::Xor; 403 case RK_FloatMult: 404 return Instruction::FMul; 405 case RK_FloatAdd: 406 return Instruction::FAdd; 407 case RK_IntegerMinMax: 408 return Instruction::ICmp; 409 case RK_FloatMinMax: 410 return Instruction::FCmp; 411 default: 412 llvm_unreachable("Unknown reduction operation"); 413 } 414 } 415 416 Value * 417 ReductionDescriptor::createMinMaxOp(IRBuilder<> &Builder, 418 ReductionInstDesc::MinMaxReductionKind RK, 419 Value *Left, Value *Right) { 420 CmpInst::Predicate P = CmpInst::ICMP_NE; 421 switch (RK) { 422 default: 423 llvm_unreachable("Unknown min/max reduction kind"); 424 case ReductionInstDesc::MRK_UIntMin: 425 P = CmpInst::ICMP_ULT; 426 break; 427 case ReductionInstDesc::MRK_UIntMax: 428 P = CmpInst::ICMP_UGT; 429 break; 430 case ReductionInstDesc::MRK_SIntMin: 431 P = CmpInst::ICMP_SLT; 432 break; 433 case ReductionInstDesc::MRK_SIntMax: 434 P = CmpInst::ICMP_SGT; 435 break; 436 case ReductionInstDesc::MRK_FloatMin: 437 P = CmpInst::FCMP_OLT; 438 break; 439 case ReductionInstDesc::MRK_FloatMax: 440 P = CmpInst::FCMP_OGT; 441 break; 442 } 443 444 Value *Cmp; 445 if (RK == ReductionInstDesc::MRK_FloatMin || 446 RK == ReductionInstDesc::MRK_FloatMax) 447 Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); 448 else 449 Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); 450 451 Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); 452 return Select; 453 } 454