lib/Transforms/Scalar/LoopUnrollPass.cpp

   1 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
   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 pass implements a simple loop unroller.  It works best when loops have
  11 // been canonicalized by the -indvars pass, allowing it to determine the trip
  12 // counts of loops easily.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Scalar.h"
  16 #include "llvm/ADT/SetVector.h"
  17 #include "llvm/Analysis/GlobalsModRef.h"
  18 #include "llvm/Analysis/AssumptionCache.h"
  19 #include "llvm/Analysis/CodeMetrics.h"
  20 #include "llvm/Analysis/InstructionSimplify.h"
  21 #include "llvm/Analysis/LoopPass.h"
  22 #include "llvm/Analysis/ScalarEvolution.h"
  23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  24 #include "llvm/Analysis/TargetTransformInfo.h"
  25 #include "llvm/IR/DataLayout.h"
  26 #include "llvm/IR/DiagnosticInfo.h"
  27 #include "llvm/IR/Dominators.h"
  28 #include "llvm/IR/InstVisitor.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/Metadata.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Transforms/Utils/UnrollLoop.h"
  35 #include <climits>
  36
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "loop-unroll"
  40
  41 static cl::opt<unsigned>
  42     UnrollThreshold("unroll-threshold", cl::Hidden,
  43                     cl::desc("The baseline cost threshold for loop unrolling"));
  44
  45 static cl::opt<unsigned> UnrollPercentDynamicCostSavedThreshold(
  46     "unroll-percent-dynamic-cost-saved-threshold", cl::Hidden,
  47     cl::desc("The percentage of estimated dynamic cost which must be saved by "
  48              "unrolling to allow unrolling up to the max threshold."));
  49
  50 static cl::opt<unsigned> UnrollDynamicCostSavingsDiscount(
  51     "unroll-dynamic-cost-savings-discount", cl::Hidden,
  52     cl::desc("This is the amount discounted from the total unroll cost when "
  53              "the unrolled form has a high dynamic cost savings (triggered by "
  54              "the '-unroll-perecent-dynamic-cost-saved-threshold' flag)."));
  55
  56 static cl::opt<unsigned> UnrollMaxIterationsCountToAnalyze(
  57     "unroll-max-iteration-count-to-analyze", cl::init(0), cl::Hidden,
  58     cl::desc("Don't allow loop unrolling to simulate more than this number of"
  59              "iterations when checking full unroll profitability"));
  60
  61 static cl::opt<unsigned>
  62 UnrollCount("unroll-count", cl::Hidden,
  63   cl::desc("Use this unroll count for all loops including those with "
  64            "unroll_count pragma values, for testing purposes"));
  65
  66 static cl::opt<bool>
  67 UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
  68   cl::desc("Allows loops to be partially unrolled until "
  69            "-unroll-threshold loop size is reached."));
  70
  71 static cl::opt<bool>
  72 UnrollRuntime("unroll-runtime", cl::ZeroOrMore, cl::Hidden,
  73   cl::desc("Unroll loops with run-time trip counts"));
  74
  75 static cl::opt<unsigned>
  76 PragmaUnrollThreshold("pragma-unroll-threshold", cl::init(16 * 1024), cl::Hidden,
  77   cl::desc("Unrolled size limit for loops with an unroll(full) or "
  78            "unroll_count pragma."));
  79
  80
  81 /// A magic value for use with the Threshold parameter to indicate
  82 /// that the loop unroll should be performed regardless of how much
  83 /// code expansion would result.
  84 static const unsigned NoThreshold = UINT_MAX;
  85
  86 /// Default unroll count for loops with run-time trip count if
  87 /// -unroll-count is not set
  88 static const unsigned DefaultUnrollRuntimeCount = 8;
  89
  90 /// Gather the various unrolling parameters based on the defaults, compiler
  91 /// flags, TTI overrides, pragmas, and user specified parameters.
  92 static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
  93     Loop *L, const TargetTransformInfo &TTI, Optional<unsigned> UserThreshold,
  94     Optional<unsigned> UserCount, Optional<bool> UserAllowPartial,
  95     Optional<bool> UserRuntime, unsigned PragmaCount, bool PragmaFullUnroll,
  96     bool PragmaEnableUnroll, unsigned TripCount) {
  97   TargetTransformInfo::UnrollingPreferences UP;
  98
  99   // Set up the defaults
 100   UP.Threshold = 150;
 101   UP.PercentDynamicCostSavedThreshold = 20;
 102   UP.DynamicCostSavingsDiscount = 2000;
 103   UP.OptSizeThreshold = 50;
 104   UP.PartialThreshold = UP.Threshold;
 105   UP.PartialOptSizeThreshold = UP.OptSizeThreshold;
 106   UP.Count = 0;
 107   UP.MaxCount = UINT_MAX;
 108   UP.Partial = false;
 109   UP.Runtime = false;
 110   UP.AllowExpensiveTripCount = false;
 111
 112   // Override with any target specific settings
 113   TTI.getUnrollingPreferences(L, UP);
 114
 115   // Apply size attributes
 116   if (L->getHeader()->getParent()->optForSize()) {
 117     UP.Threshold = UP.OptSizeThreshold;
 118     UP.PartialThreshold = UP.PartialOptSizeThreshold;
 119   }
 120
 121   // Apply unroll count pragmas
 122   if (PragmaCount)
 123     UP.Count = PragmaCount;
 124   else if (PragmaFullUnroll)
 125     UP.Count = TripCount;
 126
 127   // Apply any user values specified by cl::opt
 128   if (UnrollThreshold.getNumOccurrences() > 0) {
 129     UP.Threshold = UnrollThreshold;
 130     UP.PartialThreshold = UnrollThreshold;
 131   }
 132   if (UnrollPercentDynamicCostSavedThreshold.getNumOccurrences() > 0)
 133     UP.PercentDynamicCostSavedThreshold =
 134         UnrollPercentDynamicCostSavedThreshold;
 135   if (UnrollDynamicCostSavingsDiscount.getNumOccurrences() > 0)
 136     UP.DynamicCostSavingsDiscount = UnrollDynamicCostSavingsDiscount;
 137   if (UnrollCount.getNumOccurrences() > 0)
 138     UP.Count = UnrollCount;
 139   if (UnrollAllowPartial.getNumOccurrences() > 0)
 140     UP.Partial = UnrollAllowPartial;
 141   if (UnrollRuntime.getNumOccurrences() > 0)
 142     UP.Runtime = UnrollRuntime;
 143
 144   // Apply user values provided by argument
 145   if (UserThreshold.hasValue()) {
 146     UP.Threshold = *UserThreshold;
 147     UP.PartialThreshold = *UserThreshold;
 148   }
 149   if (UserCount.hasValue())
 150     UP.Count = *UserCount;
 151   if (UserAllowPartial.hasValue())
 152     UP.Partial = *UserAllowPartial;
 153   if (UserRuntime.hasValue())
 154     UP.Runtime = *UserRuntime;
 155
 156   if (PragmaCount > 0 ||
 157       ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount != 0)) {
 158     // If the loop has an unrolling pragma, we want to be more aggressive with
 159     // unrolling limits. Set thresholds to at least the PragmaTheshold value
 160     // which is larger than the default limits.
 161     if (UP.Threshold != NoThreshold)
 162       UP.Threshold = std::max<unsigned>(UP.Threshold, PragmaUnrollThreshold);
 163     if (UP.PartialThreshold != NoThreshold)
 164       UP.PartialThreshold =
 165           std::max<unsigned>(UP.PartialThreshold, PragmaUnrollThreshold);
 166   }
 167
 168   return UP;
 169 }
 170
 171 namespace {
 172 // This class is used to get an estimate of the optimization effects that we
 173 // could get from complete loop unrolling. It comes from the fact that some
 174 // loads might be replaced with concrete constant values and that could trigger
 175 // a chain of instruction simplifications.
 176 //
 177 // E.g. we might have:
 178 //   int a[] = {0, 1, 0};
 179 //   v = 0;
 180 //   for (i = 0; i < 3; i ++)
 181 //     v += b[i]*a[i];
 182 // If we completely unroll the loop, we would get:
 183 //   v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
 184 // Which then will be simplified to:
 185 //   v = b[0]* 0 + b[1]* 1 + b[2]* 0
 186 // And finally:
 187 //   v = b[1]
 188 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
 189   typedef InstVisitor<UnrolledInstAnalyzer, bool> Base;
 190   friend class InstVisitor<UnrolledInstAnalyzer, bool>;
 191   struct SimplifiedAddress {
 192     Value *Base = nullptr;
 193     ConstantInt *Offset = nullptr;
 194   };
 195
 196 public:
 197   UnrolledInstAnalyzer(unsigned Iteration,
 198                        DenseMap<Value *, Constant *> &SimplifiedValues,
 199                        ScalarEvolution &SE)
 200       : SimplifiedValues(SimplifiedValues), SE(SE) {
 201       IterationNumber = SE.getConstant(APInt(64, Iteration));
 202   }
 203
 204   // Allow access to the initial visit method.
 205   using Base::visit;
 206
 207 private:
 208   /// \brief A cache of pointer bases and constant-folded offsets corresponding
 209   /// to GEP (or derived from GEP) instructions.
 210   ///
 211   /// In order to find the base pointer one needs to perform non-trivial
 212   /// traversal of the corresponding SCEV expression, so it's good to have the
 213   /// results saved.
 214   DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
 215
 216   /// \brief SCEV expression corresponding to number of currently simulated
 217   /// iteration.
 218   const SCEV *IterationNumber;
 219
 220   /// \brief A Value->Constant map for keeping values that we managed to
 221   /// constant-fold on the given iteration.
 222   ///
 223   /// While we walk the loop instructions, we build up and maintain a mapping
 224   /// of simplified values specific to this iteration.  The idea is to propagate
 225   /// any special information we have about loads that can be replaced with
 226   /// constants after complete unrolling, and account for likely simplifications
 227   /// post-unrolling.
 228   DenseMap<Value *, Constant *> &SimplifiedValues;
 229
 230   ScalarEvolution &SE;
 231
 232   /// \brief Try to simplify instruction \param I using its SCEV expression.
 233   ///
 234   /// The idea is that some AddRec expressions become constants, which then
 235   /// could trigger folding of other instructions. However, that only happens
 236   /// for expressions whose start value is also constant, which isn't always the
 237   /// case. In another common and important case the start value is just some
 238   /// address (i.e. SCEVUnknown) - in this case we compute the offset and save
 239   /// it along with the base address instead.
 240   bool simplifyInstWithSCEV(Instruction *I) {
 241     if (!SE.isSCEVable(I->getType()))
 242       return false;
 243
 244     const SCEV *S = SE.getSCEV(I);
 245     if (auto *SC = dyn_cast<SCEVConstant>(S)) {
 246       SimplifiedValues[I] = SC->getValue();
 247       return true;
 248     }
 249
 250     auto *AR = dyn_cast<SCEVAddRecExpr>(S);
 251     if (!AR)
 252       return false;
 253
 254     const SCEV *ValueAtIteration = AR->evaluateAtIteration(IterationNumber, SE);
 255     // Check if the AddRec expression becomes a constant.
 256     if (auto *SC = dyn_cast<SCEVConstant>(ValueAtIteration)) {
 257       SimplifiedValues[I] = SC->getValue();
 258       return true;
 259     }
 260
 261     // Check if the offset from the base address becomes a constant.
 262     auto *Base = dyn_cast<SCEVUnknown>(SE.getPointerBase(S));
 263     if (!Base)
 264       return false;
 265     auto *Offset =
 266         dyn_cast<SCEVConstant>(SE.getMinusSCEV(ValueAtIteration, Base));
 267     if (!Offset)
 268       return false;
 269     SimplifiedAddress Address;
 270     Address.Base = Base->getValue();
 271     Address.Offset = Offset->getValue();
 272     SimplifiedAddresses[I] = Address;
 273     return true;
 274   }
 275
 276   /// Base case for the instruction visitor.
 277   bool visitInstruction(Instruction &I) {
 278     return simplifyInstWithSCEV(&I);
 279   }
 280
 281   /// Try to simplify binary operator I.
 282   ///
 283   /// TODO: Probably it's worth to hoist the code for estimating the
 284   /// simplifications effects to a separate class, since we have a very similar
 285   /// code in InlineCost already.
 286   bool visitBinaryOperator(BinaryOperator &I) {
 287     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 288     if (!isa<Constant>(LHS))
 289       if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
 290         LHS = SimpleLHS;
 291     if (!isa<Constant>(RHS))
 292       if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
 293         RHS = SimpleRHS;
 294
 295     Value *SimpleV = nullptr;
 296     const DataLayout &DL = I.getModule()->getDataLayout();
 297     if (auto FI = dyn_cast<FPMathOperator>(&I))
 298       SimpleV =
 299           SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
 300     else
 301       SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
 302
 303     if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
 304       SimplifiedValues[&I] = C;
 305
 306     if (SimpleV)
 307       return true;
 308     return Base::visitBinaryOperator(I);
 309   }
 310
 311   /// Try to fold load I.
 312   bool visitLoad(LoadInst &I) {
 313     Value *AddrOp = I.getPointerOperand();
 314
 315     auto AddressIt = SimplifiedAddresses.find(AddrOp);
 316     if (AddressIt == SimplifiedAddresses.end())
 317       return false;
 318     ConstantInt *SimplifiedAddrOp = AddressIt->second.Offset;
 319
 320     auto *GV = dyn_cast<GlobalVariable>(AddressIt->second.Base);
 321     // We're only interested in loads that can be completely folded to a
 322     // constant.
 323     if (!GV || !GV->hasDefinitiveInitializer() || !GV->isConstant())
 324       return false;
 325
 326     ConstantDataSequential *CDS =
 327         dyn_cast<ConstantDataSequential>(GV->getInitializer());
 328     if (!CDS)
 329       return false;
 330
 331     // We might have a vector load from an array. FIXME: for now we just bail
 332     // out in this case, but we should be able to resolve and simplify such
 333     // loads.
 334     if(!CDS->isElementTypeCompatible(I.getType()))
 335       return false;
 336
 337     int ElemSize = CDS->getElementType()->getPrimitiveSizeInBits() / 8U;
 338     assert(SimplifiedAddrOp->getValue().getActiveBits() < 64 &&
 339            "Unexpectedly large index value.");
 340     int64_t Index = SimplifiedAddrOp->getSExtValue() / ElemSize;
 341     if (Index >= CDS->getNumElements()) {
 342       // FIXME: For now we conservatively ignore out of bound accesses, but
 343       // we're allowed to perform the optimization in this case.
 344       return false;
 345     }
 346
 347     Constant *CV = CDS->getElementAsConstant(Index);
 348     assert(CV && "Constant expected.");
 349     SimplifiedValues[&I] = CV;
 350
 351     return true;
 352   }
 353
 354   bool visitCastInst(CastInst &I) {
 355     // Propagate constants through casts.
 356     Constant *COp = dyn_cast<Constant>(I.getOperand(0));
 357     if (!COp)
 358       COp = SimplifiedValues.lookup(I.getOperand(0));
 359     if (COp)
 360       if (Constant *C =
 361               ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
 362         SimplifiedValues[&I] = C;
 363         return true;
 364       }
 365
 366     return Base::visitCastInst(I);
 367   }
 368
 369   bool visitCmpInst(CmpInst &I) {
 370     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 371
 372     // First try to handle simplified comparisons.
 373     if (!isa<Constant>(LHS))
 374       if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
 375         LHS = SimpleLHS;
 376     if (!isa<Constant>(RHS))
 377       if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
 378         RHS = SimpleRHS;
 379
 380     if (!isa<Constant>(LHS) && !isa<Constant>(RHS)) {
 381       auto SimplifiedLHS = SimplifiedAddresses.find(LHS);
 382       if (SimplifiedLHS != SimplifiedAddresses.end()) {
 383         auto SimplifiedRHS = SimplifiedAddresses.find(RHS);
 384         if (SimplifiedRHS != SimplifiedAddresses.end()) {
 385           SimplifiedAddress &LHSAddr = SimplifiedLHS->second;
 386           SimplifiedAddress &RHSAddr = SimplifiedRHS->second;
 387           if (LHSAddr.Base == RHSAddr.Base) {
 388             LHS = LHSAddr.Offset;
 389             RHS = RHSAddr.Offset;
 390           }
 391         }
 392       }
 393     }
 394
 395     if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
 396       if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
 397         if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
 398           SimplifiedValues[&I] = C;
 399           return true;
 400         }
 401       }
 402     }
 403
 404     return Base::visitCmpInst(I);
 405   }
 406 };
 407 } // namespace
 408
 409
 410 namespace {
 411 struct EstimatedUnrollCost {
 412   /// \brief The estimated cost after unrolling.
 413   int UnrolledCost;
 414
 415   /// \brief The estimated dynamic cost of executing the instructions in the
 416   /// rolled form.
 417   int RolledDynamicCost;
 418 };
 419 }
 420
 421 /// \brief Figure out if the loop is worth full unrolling.
 422 ///
 423 /// Complete loop unrolling can make some loads constant, and we need to know
 424 /// if that would expose any further optimization opportunities.  This routine
 425 /// estimates this optimization.  It computes cost of unrolled loop
 426 /// (UnrolledCost) and dynamic cost of the original loop (RolledDynamicCost). By
 427 /// dynamic cost we mean that we won't count costs of blocks that are known not
 428 /// to be executed (i.e. if we have a branch in the loop and we know that at the
 429 /// given iteration its condition would be resolved to true, we won't add up the
 430 /// cost of the 'false'-block).
 431 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
 432 /// the analysis failed (no benefits expected from the unrolling, or the loop is
 433 /// too big to analyze), the returned value is None.
 434 static Optional<EstimatedUnrollCost>
 435 analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT,
 436                       ScalarEvolution &SE, const TargetTransformInfo &TTI,
 437                       int MaxUnrolledLoopSize) {
 438   // We want to be able to scale offsets by the trip count and add more offsets
 439   // to them without checking for overflows, and we already don't want to
 440   // analyze *massive* trip counts, so we force the max to be reasonably small.
 441   assert(UnrollMaxIterationsCountToAnalyze < (INT_MAX / 2) &&
 442          "The unroll iterations max is too large!");
 443
 444   // Don't simulate loops with a big or unknown tripcount
 445   if (!UnrollMaxIterationsCountToAnalyze || !TripCount ||
 446       TripCount > UnrollMaxIterationsCountToAnalyze)
 447     return None;
 448
 449   SmallSetVector<BasicBlock *, 16> BBWorklist;
 450   DenseMap<Value *, Constant *> SimplifiedValues;
 451   SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
 452
 453   // The estimated cost of the unrolled form of the loop. We try to estimate
 454   // this by simplifying as much as we can while computing the estimate.
 455   int UnrolledCost = 0;
 456   // We also track the estimated dynamic (that is, actually executed) cost in
 457   // the rolled form. This helps identify cases when the savings from unrolling
 458   // aren't just exposing dead control flows, but actual reduced dynamic
 459   // instructions due to the simplifications which we expect to occur after
 460   // unrolling.
 461   int RolledDynamicCost = 0;
 462
 463   // Ensure that we don't violate the loop structure invariants relied on by
 464   // this analysis.
 465   assert(L->isLoopSimplifyForm() && "Must put loop into normal form first.");
 466   assert(L->isLCSSAForm(DT) &&
 467          "Must have loops in LCSSA form to track live-out values.");
 468
 469   DEBUG(dbgs() << "Starting LoopUnroll profitability analysis...\n");
 470
 471   // Simulate execution of each iteration of the loop counting instructions,
 472   // which would be simplified.
 473   // Since the same load will take different values on different iterations,
 474   // we literally have to go through all loop's iterations.
 475   for (unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
 476     DEBUG(dbgs() << " Analyzing iteration " << Iteration << "\n");
 477
 478     // Prepare for the iteration by collecting any simplified entry or backedge
 479     // inputs.
 480     for (Instruction &I : *L->getHeader()) {
 481       auto *PHI = dyn_cast<PHINode>(&I);
 482       if (!PHI)
 483         break;
 484
 485       // The loop header PHI nodes must have exactly two input: one from the
 486       // loop preheader and one from the loop latch.
 487       assert(
 488           PHI->getNumIncomingValues() == 2 &&
 489           "Must have an incoming value only for the preheader and the latch.");
 490
 491       Value *V = PHI->getIncomingValueForBlock(
 492           Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
 493       Constant *C = dyn_cast<Constant>(V);
 494       if (Iteration != 0 && !C)
 495         C = SimplifiedValues.lookup(V);
 496       if (C)
 497         SimplifiedInputValues.push_back({PHI, C});
 498     }
 499
 500     // Now clear and re-populate the map for the next iteration.
 501     SimplifiedValues.clear();
 502     while (!SimplifiedInputValues.empty())
 503       SimplifiedValues.insert(SimplifiedInputValues.pop_back_val());
 504
 505     UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, SE);
 506
 507     BBWorklist.clear();
 508     BBWorklist.insert(L->getHeader());
 509     // Note that we *must not* cache the size, this loop grows the worklist.
 510     for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
 511       BasicBlock *BB = BBWorklist[Idx];
 512
 513       // Visit all instructions in the given basic block and try to simplify
 514       // it.  We don't change the actual IR, just count optimization
 515       // opportunities.
 516       for (Instruction &I : *BB) {
 517         int InstCost = TTI.getUserCost(&I);
 518
 519         // Visit the instruction to analyze its loop cost after unrolling,
 520         // and if the visitor returns false, include this instruction in the
 521         // unrolled cost.
 522         if (!Analyzer.visit(I))
 523           UnrolledCost += InstCost;
 524         else {
 525           DEBUG(dbgs() << "  " << I
 526                        << " would be simplified if loop is unrolled.\n");
 527           (void)0;
 528         }
 529
 530         // Also track this instructions expected cost when executing the rolled
 531         // loop form.
 532         RolledDynamicCost += InstCost;
 533
 534         // If unrolled body turns out to be too big, bail out.
 535         if (UnrolledCost > MaxUnrolledLoopSize) {
 536           DEBUG(dbgs() << "  Exceeded threshold.. exiting.\n"
 537                        << "  UnrolledCost: " << UnrolledCost
 538                        << ", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
 539                        << "\n");
 540           return None;
 541         }
 542       }
 543
 544       TerminatorInst *TI = BB->getTerminator();
 545
 546       // Add in the live successors by first checking whether we have terminator
 547       // that may be simplified based on the values simplified by this call.
 548       if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 549         if (BI->isConditional()) {
 550           if (Constant *SimpleCond =
 551                   SimplifiedValues.lookup(BI->getCondition())) {
 552             BasicBlock *Succ = nullptr;
 553             // Just take the first successor if condition is undef
 554             if (isa<UndefValue>(SimpleCond))
 555               Succ = BI->getSuccessor(0);
 556             else
 557               Succ = BI->getSuccessor(
 558                   cast<ConstantInt>(SimpleCond)->isZero() ? 1 : 0);
 559             if (L->contains(Succ))
 560               BBWorklist.insert(Succ);
 561             continue;
 562           }
 563         }
 564       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 565         if (Constant *SimpleCond =
 566                 SimplifiedValues.lookup(SI->getCondition())) {
 567           BasicBlock *Succ = nullptr;
 568           // Just take the first successor if condition is undef
 569           if (isa<UndefValue>(SimpleCond))
 570             Succ = SI->getSuccessor(0);
 571           else
 572             Succ = SI->findCaseValue(cast<ConstantInt>(SimpleCond))
 573                        .getCaseSuccessor();
 574           if (L->contains(Succ))
 575             BBWorklist.insert(Succ);
 576           continue;
 577         }
 578       }
 579
 580       // Add BB's successors to the worklist.
 581       for (BasicBlock *Succ : successors(BB))
 582         if (L->contains(Succ))
 583           BBWorklist.insert(Succ);
 584     }
 585
 586     // If we found no optimization opportunities on the first iteration, we
 587     // won't find them on later ones too.
 588     if (UnrolledCost == RolledDynamicCost) {
 589       DEBUG(dbgs() << "  No opportunities found.. exiting.\n"
 590                    << "  UnrolledCost: " << UnrolledCost << "\n");
 591       return None;
 592     }
 593   }
 594   DEBUG(dbgs() << "Analysis finished:\n"
 595                << "UnrolledCost: " << UnrolledCost << ", "
 596                << "RolledDynamicCost: " << RolledDynamicCost << "\n");
 597   return {{UnrolledCost, RolledDynamicCost}};
 598 }
 599
 600 /// ApproximateLoopSize - Approximate the size of the loop.
 601 static unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
 602                                     bool &NotDuplicatable,
 603                                     const TargetTransformInfo &TTI,
 604                                     AssumptionCache *AC) {
 605   SmallPtrSet<const Value *, 32> EphValues;
 606   CodeMetrics::collectEphemeralValues(L, AC, EphValues);
 607
 608   CodeMetrics Metrics;
 609   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
 610        I != E; ++I)
 611     Metrics.analyzeBasicBlock(*I, TTI, EphValues);
 612   NumCalls = Metrics.NumInlineCandidates;
 613   NotDuplicatable = Metrics.notDuplicatable;
 614
 615   unsigned LoopSize = Metrics.NumInsts;
 616
 617   // Don't allow an estimate of size zero.  This would allows unrolling of loops
 618   // with huge iteration counts, which is a compile time problem even if it's
 619   // not a problem for code quality. Also, the code using this size may assume
 620   // that each loop has at least three instructions (likely a conditional
 621   // branch, a comparison feeding that branch, and some kind of loop increment
 622   // feeding that comparison instruction).
 623   LoopSize = std::max(LoopSize, 3u);
 624
 625   return LoopSize;
 626 }
 627
 628 // Returns the loop hint metadata node with the given name (for example,
 629 // "llvm.loop.unroll.count").  If no such metadata node exists, then nullptr is
 630 // returned.
 631 static MDNode *GetUnrollMetadataForLoop(const Loop *L, StringRef Name) {
 632   if (MDNode *LoopID = L->getLoopID())
 633     return GetUnrollMetadata(LoopID, Name);
 634   return nullptr;
 635 }
 636
 637 // Returns true if the loop has an unroll(full) pragma.
 638 static bool HasUnrollFullPragma(const Loop *L) {
 639   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.full");
 640 }
 641
 642 // Returns true if the loop has an unroll(enable) pragma. This metadata is used
 643 // for both "#pragma unroll" and "#pragma clang loop unroll(enable)" directives.
 644 static bool HasUnrollEnablePragma(const Loop *L) {
 645   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.enable");
 646 }
 647
 648 // Returns true if the loop has an unroll(disable) pragma.
 649 static bool HasUnrollDisablePragma(const Loop *L) {
 650   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.disable");
 651 }
 652
 653 // Returns true if the loop has an runtime unroll(disable) pragma.
 654 static bool HasRuntimeUnrollDisablePragma(const Loop *L) {
 655   return GetUnrollMetadataForLoop(L, "llvm.loop.unroll.runtime.disable");
 656 }
 657
 658 // If loop has an unroll_count pragma return the (necessarily
 659 // positive) value from the pragma.  Otherwise return 0.
 660 static unsigned UnrollCountPragmaValue(const Loop *L) {
 661   MDNode *MD = GetUnrollMetadataForLoop(L, "llvm.loop.unroll.count");
 662   if (MD) {
 663     assert(MD->getNumOperands() == 2 &&
 664            "Unroll count hint metadata should have two operands.");
 665     unsigned Count =
 666         mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
 667     assert(Count >= 1 && "Unroll count must be positive.");
 668     return Count;
 669   }
 670   return 0;
 671 }
 672
 673 // Remove existing unroll metadata and add unroll disable metadata to
 674 // indicate the loop has already been unrolled.  This prevents a loop
 675 // from being unrolled more than is directed by a pragma if the loop
 676 // unrolling pass is run more than once (which it generally is).
 677 static void SetLoopAlreadyUnrolled(Loop *L) {
 678   MDNode *LoopID = L->getLoopID();
 679   if (!LoopID) return;
 680
 681   // First remove any existing loop unrolling metadata.
 682   SmallVector<Metadata *, 4> MDs;
 683   // Reserve first location for self reference to the LoopID metadata node.
 684   MDs.push_back(nullptr);
 685   for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 686     bool IsUnrollMetadata = false;
 687     MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
 688     if (MD) {
 689       const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 690       IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
 691     }
 692     if (!IsUnrollMetadata)
 693       MDs.push_back(LoopID->getOperand(i));
 694   }
 695
 696   // Add unroll(disable) metadata to disable future unrolling.
 697   LLVMContext &Context = L->getHeader()->getContext();
 698   SmallVector<Metadata *, 1> DisableOperands;
 699   DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
 700   MDNode *DisableNode = MDNode::get(Context, DisableOperands);
 701   MDs.push_back(DisableNode);
 702
 703   MDNode *NewLoopID = MDNode::get(Context, MDs);
 704   // Set operand 0 to refer to the loop id itself.
 705   NewLoopID->replaceOperandWith(0, NewLoopID);
 706   L->setLoopID(NewLoopID);
 707 }
 708
 709 static bool canUnrollCompletely(Loop *L, unsigned Threshold,
 710                                 unsigned PercentDynamicCostSavedThreshold,
 711                                 unsigned DynamicCostSavingsDiscount,
 712                                 uint64_t UnrolledCost,
 713                                 uint64_t RolledDynamicCost) {
 714   if (Threshold == NoThreshold) {
 715     DEBUG(dbgs() << "  Can fully unroll, because no threshold is set.\n");
 716     return true;
 717   }
 718
 719   if (UnrolledCost <= Threshold) {
 720     DEBUG(dbgs() << "  Can fully unroll, because unrolled cost: "
 721                  << UnrolledCost << "<" << Threshold << "\n");
 722     return true;
 723   }
 724
 725   assert(UnrolledCost && "UnrolledCost can't be 0 at this point.");
 726   assert(RolledDynamicCost >= UnrolledCost &&
 727          "Cannot have a higher unrolled cost than a rolled cost!");
 728
 729   // Compute the percentage of the dynamic cost in the rolled form that is
 730   // saved when unrolled. If unrolling dramatically reduces the estimated
 731   // dynamic cost of the loop, we use a higher threshold to allow more
 732   // unrolling.
 733   unsigned PercentDynamicCostSaved =
 734       (uint64_t)(RolledDynamicCost - UnrolledCost) * 100ull / RolledDynamicCost;
 735
 736   if (PercentDynamicCostSaved >= PercentDynamicCostSavedThreshold &&
 737       (int64_t)UnrolledCost - (int64_t)DynamicCostSavingsDiscount <=
 738           (int64_t)Threshold) {
 739     DEBUG(dbgs() << "  Can fully unroll, because unrolling will reduce the "
 740                     "expected dynamic cost by " << PercentDynamicCostSaved
 741                  << "% (threshold: " << PercentDynamicCostSavedThreshold
 742                  << "%)\n"
 743                  << "  and the unrolled cost (" << UnrolledCost
 744                  << ") is less than the max threshold ("
 745                  << DynamicCostSavingsDiscount << ").\n");
 746     return true;
 747   }
 748
 749   DEBUG(dbgs() << "  Too large to fully unroll:\n");
 750   DEBUG(dbgs() << "    Threshold: " << Threshold << "\n");
 751   DEBUG(dbgs() << "    Max threshold: " << DynamicCostSavingsDiscount << "\n");
 752   DEBUG(dbgs() << "    Percent cost saved threshold: "
 753                << PercentDynamicCostSavedThreshold << "%\n");
 754   DEBUG(dbgs() << "    Unrolled cost: " << UnrolledCost << "\n");
 755   DEBUG(dbgs() << "    Rolled dynamic cost: " << RolledDynamicCost << "\n");
 756   DEBUG(dbgs() << "    Percent cost saved: " << PercentDynamicCostSaved
 757                << "\n");
 758   return false;
 759 }
 760
 761 static bool tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
 762                             ScalarEvolution *SE, const TargetTransformInfo &TTI,
 763                             AssumptionCache &AC, bool PreserveLCSSA,
 764                             Optional<unsigned> ProvidedCount,
 765                             Optional<unsigned> ProvidedThreshold,
 766                             Optional<bool> ProvidedAllowPartial,
 767                             Optional<bool> ProvidedRuntime) {
 768   BasicBlock *Header = L->getHeader();
 769   DEBUG(dbgs() << "Loop Unroll: F[" << Header->getParent()->getName()
 770         << "] Loop %" << Header->getName() << "\n");
 771
 772   if (HasUnrollDisablePragma(L)) {
 773     return false;
 774   }
 775   bool PragmaFullUnroll = HasUnrollFullPragma(L);
 776   bool PragmaEnableUnroll = HasUnrollEnablePragma(L);
 777   unsigned PragmaCount = UnrollCountPragmaValue(L);
 778   bool HasPragma = PragmaFullUnroll || PragmaEnableUnroll || PragmaCount > 0;
 779
 780   // Find trip count and trip multiple if count is not available
 781   unsigned TripCount = 0;
 782   unsigned TripMultiple = 1;
 783   // If there are multiple exiting blocks but one of them is the latch, use the
 784   // latch for the trip count estimation. Otherwise insist on a single exiting
 785   // block for the trip count estimation.
 786   BasicBlock *ExitingBlock = L->getLoopLatch();
 787   if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
 788     ExitingBlock = L->getExitingBlock();
 789   if (ExitingBlock) {
 790     TripCount = SE->getSmallConstantTripCount(L, ExitingBlock);
 791     TripMultiple = SE->getSmallConstantTripMultiple(L, ExitingBlock);
 792   }
 793
 794   TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
 795       L, TTI, ProvidedThreshold, ProvidedCount, ProvidedAllowPartial,
 796       ProvidedRuntime, PragmaCount, PragmaFullUnroll, PragmaEnableUnroll,
 797       TripCount);
 798
 799   unsigned Count = UP.Count;
 800   bool CountSetExplicitly = Count != 0;
 801   // Use a heuristic count if we didn't set anything explicitly.
 802   if (!CountSetExplicitly)
 803     Count = TripCount == 0 ? DefaultUnrollRuntimeCount : TripCount;
 804   if (TripCount && Count > TripCount)
 805     Count = TripCount;
 806
 807   unsigned NumInlineCandidates;
 808   bool notDuplicatable;
 809   unsigned LoopSize =
 810       ApproximateLoopSize(L, NumInlineCandidates, notDuplicatable, TTI, &AC);
 811   DEBUG(dbgs() << "  Loop Size = " << LoopSize << "\n");
 812
 813   // When computing the unrolled size, note that the conditional branch on the
 814   // backedge and the comparison feeding it are not replicated like the rest of
 815   // the loop body (which is why 2 is subtracted).
 816   uint64_t UnrolledSize = (uint64_t)(LoopSize-2) * Count + 2;
 817   if (notDuplicatable) {
 818     DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable"
 819                  << " instructions.\n");
 820     return false;
 821   }
 822   if (NumInlineCandidates != 0) {
 823     DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
 824     return false;
 825   }
 826
 827   // Given Count, TripCount and thresholds determine the type of
 828   // unrolling which is to be performed.
 829   enum { Full = 0, Partial = 1, Runtime = 2 };
 830   int Unrolling;
 831   if (TripCount && Count == TripCount) {
 832     Unrolling = Partial;
 833     // If the loop is really small, we don't need to run an expensive analysis.
 834     if (canUnrollCompletely(L, UP.Threshold, 100, UP.DynamicCostSavingsDiscount,
 835                             UnrolledSize, UnrolledSize)) {
 836       Unrolling = Full;
 837     } else {
 838       // The loop isn't that small, but we still can fully unroll it if that
 839       // helps to remove a significant number of instructions.
 840       // To check that, run additional analysis on the loop.
 841       if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
 842               L, TripCount, DT, *SE, TTI,
 843               UP.Threshold + UP.DynamicCostSavingsDiscount))
 844         if (canUnrollCompletely(L, UP.Threshold,
 845                                 UP.PercentDynamicCostSavedThreshold,
 846                                 UP.DynamicCostSavingsDiscount,
 847                                 Cost->UnrolledCost, Cost->RolledDynamicCost)) {
 848           Unrolling = Full;
 849         }
 850     }
 851   } else if (TripCount && Count < TripCount) {
 852     Unrolling = Partial;
 853   } else {
 854     Unrolling = Runtime;
 855   }
 856
 857   // Reduce count based on the type of unrolling and the threshold values.
 858   unsigned OriginalCount = Count;
 859   bool AllowRuntime = PragmaEnableUnroll || (PragmaCount > 0) || UP.Runtime;
 860   // Don't unroll a runtime trip count loop with unroll full pragma.
 861   if (HasRuntimeUnrollDisablePragma(L) || PragmaFullUnroll) {
 862     AllowRuntime = false;
 863   }
 864   if (Unrolling == Partial) {
 865     bool AllowPartial = PragmaEnableUnroll || UP.Partial;
 866     if (!AllowPartial && !CountSetExplicitly) {
 867       DEBUG(dbgs() << "  will not try to unroll partially because "
 868                    << "-unroll-allow-partial not given\n");
 869       return false;
 870     }
 871     if (UP.PartialThreshold != NoThreshold &&
 872         UnrolledSize > UP.PartialThreshold) {
 873       // Reduce unroll count to be modulo of TripCount for partial unrolling.
 874       Count = (std::max(UP.PartialThreshold, 3u) - 2) / (LoopSize - 2);
 875       while (Count != 0 && TripCount % Count != 0)
 876         Count--;
 877     }
 878   } else if (Unrolling == Runtime) {
 879     if (!AllowRuntime && !CountSetExplicitly) {
 880       DEBUG(dbgs() << "  will not try to unroll loop with runtime trip count "
 881                    << "-unroll-runtime not given\n");
 882       return false;
 883     }
 884     // Reduce unroll count to be the largest power-of-two factor of
 885     // the original count which satisfies the threshold limit.
 886     while (Count != 0 && UnrolledSize > UP.PartialThreshold) {
 887       Count >>= 1;
 888       UnrolledSize = (LoopSize-2) * Count + 2;
 889     }
 890     if (Count > UP.MaxCount)
 891       Count = UP.MaxCount;
 892     DEBUG(dbgs() << "  partially unrolling with count: " << Count << "\n");
 893   }
 894
 895   if (HasPragma) {
 896     if (PragmaCount != 0)
 897       // If loop has an unroll count pragma mark loop as unrolled to prevent
 898       // unrolling beyond that requested by the pragma.
 899       SetLoopAlreadyUnrolled(L);
 900
 901     // Emit optimization remarks if we are unable to unroll the loop
 902     // as directed by a pragma.
 903     DebugLoc LoopLoc = L->getStartLoc();
 904     Function *F = Header->getParent();
 905     LLVMContext &Ctx = F->getContext();
 906     if ((PragmaCount > 0) && Count != OriginalCount) {
 907       emitOptimizationRemarkMissed(
 908           Ctx, DEBUG_TYPE, *F, LoopLoc,
 909           "Unable to unroll loop the number of times directed by "
 910           "unroll_count pragma because unrolled size is too large.");
 911     } else if (PragmaFullUnroll && !TripCount) {
 912       emitOptimizationRemarkMissed(
 913           Ctx, DEBUG_TYPE, *F, LoopLoc,
 914           "Unable to fully unroll loop as directed by unroll(full) pragma "
 915           "because loop has a runtime trip count.");
 916     } else if (PragmaEnableUnroll && Count != TripCount && Count < 2) {
 917       emitOptimizationRemarkMissed(
 918           Ctx, DEBUG_TYPE, *F, LoopLoc,
 919           "Unable to unroll loop as directed by unroll(enable) pragma because "
 920           "unrolled size is too large.");
 921     } else if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
 922                Count != TripCount) {
 923       emitOptimizationRemarkMissed(
 924           Ctx, DEBUG_TYPE, *F, LoopLoc,
 925           "Unable to fully unroll loop as directed by unroll pragma because "
 926           "unrolled size is too large.");
 927     }
 928   }
 929
 930   if (Unrolling != Full && Count < 2) {
 931     // Partial unrolling by 1 is a nop.  For full unrolling, a factor
 932     // of 1 makes sense because loop control can be eliminated.
 933     return false;
 934   }
 935
 936   // Unroll the loop.
 937   if (!UnrollLoop(L, Count, TripCount, AllowRuntime, UP.AllowExpensiveTripCount,
 938                   TripMultiple, LI, SE, &DT, &AC, PreserveLCSSA))
 939     return false;
 940
 941   return true;
 942 }
 943
 944 namespace {
 945 class LoopUnroll : public LoopPass {
 946 public:
 947   static char ID; // Pass ID, replacement for typeid
 948   LoopUnroll(Optional<unsigned> Threshold = None,
 949              Optional<unsigned> Count = None,
 950              Optional<bool> AllowPartial = None, Optional<bool> Runtime = None)
 951       : LoopPass(ID), ProvidedCount(Count), ProvidedThreshold(Threshold),
 952         ProvidedAllowPartial(AllowPartial), ProvidedRuntime(Runtime) {
 953     initializeLoopUnrollPass(*PassRegistry::getPassRegistry());
 954   }
 955
 956   Optional<unsigned> ProvidedCount;
 957   Optional<unsigned> ProvidedThreshold;
 958   Optional<bool> ProvidedAllowPartial;
 959   Optional<bool> ProvidedRuntime;
 960
 961   bool runOnLoop(Loop *L, LPPassManager &) override {
 962     if (skipOptnoneFunction(L))
 963       return false;
 964
 965     Function &F = *L->getHeader()->getParent();
 966
 967     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 968     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 969     ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 970     const TargetTransformInfo &TTI =
 971         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 972     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 973     bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 974
 975     return tryToUnrollLoop(L, DT, LI, SE, TTI, AC, PreserveLCSSA, ProvidedCount,
 976                            ProvidedThreshold, ProvidedAllowPartial,
 977                            ProvidedRuntime);
 978   }
 979
 980   /// This transformation requires natural loop information & requires that
 981   /// loop preheaders be inserted into the CFG...
 982   ///
 983   void getAnalysisUsage(AnalysisUsage &AU) const override {
 984     AU.addRequired<AssumptionCacheTracker>();
 985     AU.addRequired<DominatorTreeWrapperPass>();
 986     AU.addRequired<LoopInfoWrapperPass>();
 987     AU.addPreserved<LoopInfoWrapperPass>();
 988     AU.addRequiredID(LoopSimplifyID);
 989     AU.addPreservedID(LoopSimplifyID);
 990     AU.addRequiredID(LCSSAID);
 991     AU.addPreservedID(LCSSAID);
 992     AU.addRequired<ScalarEvolutionWrapperPass>();
 993     AU.addPreserved<ScalarEvolutionWrapperPass>();
 994     AU.addRequired<TargetTransformInfoWrapperPass>();
 995     // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info.
 996     // If loop unroll does not preserve dom info then LCSSA pass on next
 997     // loop will receive invalid dom info.
 998     // For now, recreate dom info, if loop is unrolled.
 999     AU.addPreserved<DominatorTreeWrapperPass>();
1000     AU.addPreserved<GlobalsAAWrapperPass>();
1001   }
1002 };
1003 }
1004
1005 char LoopUnroll::ID = 0;
1006 INITIALIZE_PASS_BEGIN(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1007 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1008 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1009 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1010 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1011 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1012 INITIALIZE_PASS_DEPENDENCY(LCSSA)
1013 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
1014 INITIALIZE_PASS_END(LoopUnroll, "loop-unroll", "Unroll loops", false, false)
1015
1016 Pass *llvm::createLoopUnrollPass(int Threshold, int Count, int AllowPartial,
1017                                  int Runtime) {
1018   // TODO: It would make more sense for this function to take the optionals
1019   // directly, but that's dangerous since it would silently break out of tree
1020   // callers.
1021   return new LoopUnroll(Threshold == -1 ? None : Optional<unsigned>(Threshold),
1022                         Count == -1 ? None : Optional<unsigned>(Count),
1023                         AllowPartial == -1 ? None
1024                                            : Optional<bool>(AllowPartial),
1025                         Runtime == -1 ? None : Optional<bool>(Runtime));
1026 }
1027
1028 Pass *llvm::createSimpleLoopUnrollPass() {
1029   return llvm::createLoopUnrollPass(-1, -1, 0, 0);
1030 }