Lines Matching full:chain
48 // - For each equivalence class, greedily build "chains". Each chain has a
49 // leader instruction, and every other member of the chain has a known
50 // constant offset from the first instr in the chain.
53 // - Convert each chain to vector instructions.
146 // A Chain is a set of instructions such that:
149 // - We know the address accessed by the i'th chain elem relative to the
150 // chain's leader instruction, which is the first instr of the chain in BB
163 using Chain = SmallVector<ChainElem, 1>;
165 void sortChainInBBOrder(Chain &C) {
169 void sortChainInOffsetOrder(Chain &C) {
189 Instruction *propagateMetadata(Instruction *I, const Chain &C) {
276 /// Runs the vectorizer on one chain, i.e. a subset of an equivalence class
279 bool runOnChain(Chain &C);
281 /// Splits the chain into subchains of instructions which read/write a
284 std::vector<Chain> splitChainByContiguity(Chain &C);
286 /// Splits the chain into subchains where it's safe to hoist loads up to the
287 /// beginning of the sub-chain and it's safe to sink loads up to the end of
288 /// the sub-chain. Discards any length-1 subchains.
289 std::vector<Chain> splitChainByMayAliasInstrs(Chain &C);
291 /// Splits the chain into subchains that make legal, aligned accesses.
293 std::vector<Chain> splitChainByAlignment(Chain &C);
295 /// Converts the instrs in the chain into a single vectorized load or store.
297 bool vectorizeChain(Chain &C);
310 /// Gets the element type of the vector that the chain will load or store.
311 /// This is nontrivial because the chain may contain elements of different
312 /// types; e.g. it's legal to have a chain that contains both i32 and float.
313 Type *getChainElemTy(const Chain &C);
341 /// constant offset from the first instr in the chain.
344 /// in the chain is the leader, and an instr touches distance 0 from itself.
345 std::vector<Chain> gatherChains(ArrayRef<Instruction *> Instrs);
500 std::vector<Chain> Chains = gatherChains(EqClass);
503 for (Chain &C : Chains)
508 bool Vectorizer::runOnChain(Chain &C) {
510 dbgs() << "LSV: Running on chain with " << C.size() << " instructions:\n";
514 // Split up the chain into increasingly smaller chains, until we can finally
528 std::vector<Chain> Vectorizer::splitChainByMayAliasInstrs(Chain &C) {
535 dbgs() << "LSV: splitChainByMayAliasInstrs considering chain:\n";
539 // We know that elements in the chain with nonverlapping offsets can't
546 // Loads get hoisted up to the first load in the chain. Stores get sunk
547 // down to the last store in the chain. Our algorithm for loads is:
549 // - Take the first element of the chain. This is the start of a new chain.
550 // - Take the next element of `Chain` and check for may-alias instructions
567 std::vector<Chain> Chains;
583 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n";
589 // Start a new chain.
595 dbgs() << "LSV: got nontrivial chain without aliasing instrs:\n";
610 std::vector<Chain> Vectorizer::splitChainByContiguity(Chain &C) {
617 dbgs() << "LSV: splitChainByContiguity considering chain:\n";
621 std::vector<Chain> Ret;
633 // Add this instruction to the end of the current chain, or start a new one.
647 llvm::erase_if(Ret, [](const auto &Chain) { return Chain.size() <= 1; });
651 Type *Vectorizer::getChainElemTy(const Chain &C) {
654 // - If there are any pointer types in the chain, use an integer type.
655 // - Prefer an integer type if it appears in the chain.
656 // - Otherwise, use the first type in the chain.
678 std::vector<Chain> Vectorizer::splitChainByAlignment(Chain &C) {
680 // - Given a chain of length N, find all prefixes that
685 // elements in the chain.
686 // - If none of them work, discard the first element and repeat on a chain
694 dbgs() << "LSV: splitChainByAlignment considering chain:\n";
719 std::vector<Chain> Ret;
735 // Consider the longest chain first.
740 dbgs() << "LSV: splitChainByAlignment considering candidate chain ["
760 dbgs() << "LSV: splitChainByAlignment discarding candidate chain "
831 dbgs() << "LSV: splitChainByAlignment discarding candidate chain "
842 dbgs() << "LSV: splitChainByAlignment discarding candidate chain "
847 // Hooray, we can vectorize this chain!
848 Chain &NewChain = Ret.emplace_back();
851 CBegin = CEnd; // Skip over the instructions we've added to the chain.
858 bool Vectorizer::vectorizeChain(Chain &C) {
865 dbgs() << "LSV: Vectorizing chain of " << C.size() << " instructions:\n";
892 // All elements of the chain must have the same scalar-type size.
901 // Loads get hoisted to the location of the first load in the chain. We may
908 // Chain is in offset order, so C[0] is the instr with the lowest offset,
955 // Stores get sunk to the location of the last store in the chain.
981 // Chain is in offset order, so C[0] is the instr with the lowest offset,
1046 // If I is in the chain, we can tell whether it aliases ChainIt by checking
1051 // split the chain so we don't have to handle this case specially.
1071 dbgs() << "LSV: Found alias in chain: " << *I << "\n";
1082 LLVM_DEBUG(dbgs() << "LSV: Found alias in chain:\n"
1502 std::vector<Chain> Vectorizer::gatherChains(ArrayRef<Instruction *> Instrs) {
1522 std::pair<Instruction *, Chain> {
1524 : std::pair<Instruction *, Chain>(I, {}) {}
1583 std::vector<Chain> Ret;
1611 // the smallest data type used in the cast/gep chain.