Lines Matching full:chain
96 // Stress test IV chain generation.
1435 /// IVInc - An individual increment in a Chain of IV increments.
1437 /// used by the previous link in the Chain.
1439 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
1440 /// original IVOperand. The head of the chain's IVOperand is only valid during
1441 /// chain collection, before LSR replaces IV users. During chain generation,
1454 // We typically add the head of a chain without finding subsequent links.
1466 // begin - return the first increment in the chain.
1475 // hasIncs - Returns true if this chain contains any increments.
1478 // add - Add an IVInc to the end of this chain.
1481 // tailUserInst - Returns the last UserInst in the chain.
1485 // this chain.
1532 // have more than a few IV increment chains in a loop. Missing a Chain falls
1536 /// IVChainVec - IV users can form a chain of IV increments.
1549 void FinalizeChain(IVChain &Chain);
1551 void GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
2310 /// isCompatibleIVType - Return true if we allow an IV chain to include both
2361 /// Return true if the chain increment is profitable to expand into a loop
2362 /// invariant value, which may require its own register. A profitable chain
2364 /// to potentially be used as chain increment as long as it's not obviously
2385 /// Return true if the number of registers needed for the chain is estimated to
2388 /// be empty). Next count the number and type of increments in the chain.
2396 isProfitableChain(IVChain &Chain, SmallPtrSet<Instruction*, 4> &Users,
2401 if (!Chain.hasIncs())
2405 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " users:\n";
2412 assert(!Chain.Incs.empty() && "empty IV chains are not allowed");
2414 // The chain itself may require a register, so intialize cost to 1.
2417 // A complete chain likely eliminates the need for keeping the original IV in
2418 // a register. LSR does not currently know how to form a complete chain unless
2420 if (isa<PHINode>(Chain.tailUserInst())
2421 && SE.getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) {
2428 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end();
2448 // An IV chain with a single increment is handled by LSR's postinc
2449 // uses. However, a chain with multiple increments requires keeping the IV's
2464 DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " Cost: " << cost
2470 /// ChainInstruction - Add this IV user to an existing chain or make it the head
2471 /// of a new chain.
2481 // profitable loop invariant increment from the last link in the Chain.
2485 IVChain &Chain = IVChainVec[ChainIdx];
2491 if (!StressIVChain && Chain.ExprBase != OperExprBase)
2494 Value *PrevIV = getWideOperand(Chain.Incs.back().IVOperand);
2498 // A phi node terminates a chain.
2499 if (isa<PHINode>(UserInst) && isa<PHINode>(Chain.tailUserInst()))
2508 if (Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) {
2513 // If we haven't found a chain, create a new one, unless we hit the max. Don't
2514 // bother for phi nodes, because they must be last in the chain.
2519 DEBUG(dbgs() << "IV Chain Limit\n");
2532 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Head: (" << *UserInst
2535 DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Inc: (" << *UserInst
2537 // Add this IV user to the end of the chain.
2540 IVChain &Chain = IVChainVec[ChainIdx];
2543 // This chain's NearUsers become FarUsers.
2550 // All other uses of IVOperand become near uses of the chain.
2552 // they will eventually be used be the current chain, or can be computed
2553 // from one of the chain increments. To be more precise we could
2560 // Uses in the chain will no longer be uses if the chain is formed.
2561 // Include the head of the chain in this iteration (not Chain.begin()).
2562 IVChain::const_iterator IncIter = Chain.Incs.begin();
2563 IVChain::const_iterator IncEnd = Chain.Incs.end();
2579 // Since this user is part of the chain, it's no longer considered a use
2580 // of the chain.
2594 /// Finding the best IV chain is potentially a scheduling problem. Since LSR
2595 /// will not reorder memory operations, it will recognize this as a chain, but
2651 // Visit phi backedges to determine if the chain can generate the IV postinc.
2669 // Preserve the chain at UsesIdx.
2678 void LSRInstance::FinalizeChain(IVChain &Chain) {
2679 assert(!Chain.Incs.empty() && "empty IV chains are not allowed");
2680 DEBUG(dbgs() << "Final Chain: " << *Chain.Incs[0].UserInst << "\n");
2682 for (IVChain::const_iterator I = Chain.begin(), E = Chain.end();
2711 /// GenerateIVChains - Generate an add or subtract for each IVInc in a chain to
2713 void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
2715 // Find the new IVOperand for the head of the chain. It may have been replaced
2717 const IVInc &Head = Chain.Incs[0];
2725 // If this operand computes the expression that the chain needs, we may use
2729 // narrow for the chain, so we can no longer use it. We do allow using a
2740 // Gracefully give up on this chain.
2741 DEBUG(dbgs() << "Concealed chain head: " << *Head.UserInst << "\n");
2745 DEBUG(dbgs() << "Generate chain at: " << *IVSrc << "\n");
2749 for (IVChain::const_iterator IncI = Chain.begin(),
2750 IncE = Chain.end(); IncI != IncE; ++IncI) {
2787 IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain");
2793 // do this if we also found a wide value for the head of the chain.
2794 if (isa<PHINode>(Chain.tailUserInst())) {
2809 IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain");
