140 lines · c
1//===- HexagonVectorLoopCarriedReuse.h ------------------------------------===//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 removes the computation of provably redundant expressions that have10// been computed earlier in a previous iteration. It relies on the use of PHIs11// to identify loop carried dependences. This is scalar replacement for vector12// types.13//14//-----------------------------------------------------------------------------15// Motivation: Consider the case where we have the following loop structure.16//17// Loop:18// t0 = a[i];19// t1 = f(t0);20// t2 = g(t1);21// ...22// t3 = a[i+1];23// t4 = f(t3);24// t5 = g(t4);25// t6 = op(t2, t5)26// cond_branch <Loop>27//28// This can be converted to29// t00 = a[0];30// t10 = f(t00);31// t20 = g(t10);32// Loop:33// t2 = t20;34// t3 = a[i+1];35// t4 = f(t3);36// t5 = g(t4);37// t6 = op(t2, t5)38// t20 = t539// cond_branch <Loop>40//41// SROA does a good job of reusing a[i+1] as a[i] in the next iteration.42// Such a loop comes to this pass in the following form.43//44// LoopPreheader:45// X0 = a[0];46// Loop:47// X2 = PHI<(X0, LoopPreheader), (X1, Loop)>48// t1 = f(X2) <-- I149// t2 = g(t1)50// ...51// X1 = a[i+1]52// t4 = f(X1) <-- I253// t5 = g(t4)54// t6 = op(t2, t5)55// cond_branch <Loop>56//57// In this pass, we look for PHIs such as X2 whose incoming values come only58// from the Loop Preheader and over the backedge and additionally, both these59// values are the results of the same operation in terms of opcode. We call such60// a PHI node a dependence chain or DepChain. In this case, the dependence of X261// over X1 is carried over only one iteration and so the DepChain is only one62// PHI node long.63//64// Then, we traverse the uses of the PHI (X2) and the uses of the value of the65// PHI coming over the backedge (X1). We stop at the first pair of such users66// I1 (of X2) and I2 (of X1) that meet the following conditions.67// 1. I1 and I2 are the same operation, but with different operands.68// 2. X2 and X1 are used at the same operand number in the two instructions.69// 3. All other operands Op1 of I1 and Op2 of I2 are also such that there is a70// a DepChain from Op1 to Op2 of the same length as that between X2 and X1.71//72// We then make the following transformation73// LoopPreheader:74// X0 = a[0];75// Y0 = f(X0);76// Loop:77// X2 = PHI<(X0, LoopPreheader), (X1, Loop)>78// Y2 = PHI<(Y0, LoopPreheader), (t4, Loop)>79// t1 = f(X2) <-- Will be removed by DCE.80// t2 = g(Y2)81// ...82// X1 = a[i+1]83// t4 = f(X1)84// t5 = g(t4)85// t6 = op(t2, t5)86// cond_branch <Loop>87//88// We proceed until we cannot find any more such instructions I1 and I2.89//90// --- DepChains & Loop carried dependences ---91// Consider a single basic block loop such as92//93// LoopPreheader:94// X0 = ...95// Y0 = ...96// Loop:97// X2 = PHI<(X0, LoopPreheader), (X1, Loop)>98// Y2 = PHI<(Y0, LoopPreheader), (X2, Loop)>99// ...100// X1 = ...101// ...102// cond_branch <Loop>103//104// Then there is a dependence between X2 and X1 that goes back one iteration,105// i.e. X1 is used as X2 in the very next iteration. We represent this as a106// DepChain from X2 to X1 (X2->X1).107// Similarly, there is a dependence between Y2 and X1 that goes back two108// iterations. X1 is used as Y2 two iterations after it is computed. This is109// represented by a DepChain as (Y2->X2->X1).110//111// A DepChain has the following properties.112// 1. Num of edges in DepChain = Number of Instructions in DepChain = Number of113// iterations of carried dependence + 1.114// 2. All instructions in the DepChain except the last are PHIs.115//116//===----------------------------------------------------------------------===//117 118#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H119#define LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H120 121#include "llvm/Transforms/Scalar/LoopPassManager.h"122 123namespace llvm {124 125class Loop;126 127/// Hexagon Vector Loop Carried Reuse Pass128struct HexagonVectorLoopCarriedReusePass129 : public PassInfoMixin<HexagonVectorLoopCarriedReusePass> {130 HexagonVectorLoopCarriedReusePass() = default;131 132 /// Run pass over the Loop.133 PreservedAnalyses run(Loop &L, LoopAnalysisManager &LAM,134 LoopStandardAnalysisResults &AR, LPMUpdater &U);135};136 137} // end namespace llvm138 139#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H140