Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- NaryReassociate.h - Reassociate n-ary expressions --------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This pass reassociates n-ary add expressions and eliminates the redundancy

// exposed by the reassociation.

//

// A motivating example:

//

//   void foo(int a, int b) {

//     bar(a + b);

//     bar((a + 2) + b);

//   }

//

// An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify

// the above code to

//

//   int t = a + b;

//   bar(t);

//   bar(t + 2);

//

// However, the Reassociate pass is unable to do that because it processes each

// instruction individually and believes (a + 2) + b is the best form according

// to its rank system.

//

// To address this limitation, NaryReassociate reassociates an expression in a

// form that reuses existing instructions. As a result, NaryReassociate can

// reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that

// (a + b) is computed before.

//

// NaryReassociate works as follows. For every instruction in the form of (a +

// b) + c, it checks whether a + c or b + c is already computed by a dominating

// instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +

// c) + a and removes the redundancy accordingly. To efficiently look up whether

// an expression is computed before, we store each instruction seen and its SCEV

// into an SCEV-to-instruction map.

//

// Although the algorithm pattern-matches only ternary additions, it

// automatically handles many >3-ary expressions by walking through the function

// in the depth-first order. For example, given

//

//   (a + c) + d

//   ((a + b) + c) + d

//

// NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites

// ((a + c) + b) + d into ((a + c) + d) + b.

//

// Finally, the above dominator-based algorithm may need to be run multiple

// iterations before emitting optimal code. One source of this need is that we

// only split an operand when it is used only once. The above algorithm can

// eliminate an instruction and decrease the usage count of its operands. As a

// result, an instruction that previously had multiple uses may become a

// single-use instruction and thus eligible for split consideration. For

// example,

//

//   ac = a + c

//   ab = a + b

//   abc = ab + c

//   ab2 = ab + b

//   ab2c = ab2 + c

//

// In the first iteration, we cannot reassociate abc to ac+b because ab is used

// twice. However, we can reassociate ab2c to abc+b in the first iteration. As a

// result, ab2 becomes dead and ab will be used only once in the second

// iteration.

//

// Limitations and TODO items:

//

// 1) We only considers n-ary adds and muls for now. This should be extended

// and generalized.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H

#define LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/ValueHandle.h"

namespace llvm {

class AssumptionCache;

class BinaryOperator;

class DataLayout;

class DominatorTree;

class Function;

class GetElementPtrInst;

class Instruction;

class ScalarEvolution;

class SCEV;

class TargetLibraryInfo;

class TargetTransformInfo;

class Type;

class Value;

class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {

public:

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

  // Glue for old PM.

  bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,

               ScalarEvolution *SE_, TargetLibraryInfo *TLI_,

               TargetTransformInfo *TTI_);

private:

  // Runs only one iteration of the dominator-based algorithm. See the header

  // comments for why we need multiple iterations.

  bool doOneIteration(Function &F);

  // Reassociates I for better CSE.

  Instruction *tryReassociate(Instruction *I, const SCEV *&OrigSCEV);

  // Reassociate GEP for better CSE.

  Instruction *tryReassociateGEP(GetElementPtrInst *GEP);

  // Try splitting GEP at the I-th index and see whether either part can be

  // CSE'ed. This is a helper function for tryReassociateGEP.

  //

  // \p IndexedType The element type indexed by GEP's I-th index. This is

  //                equivalent to

  //                  GEP->getIndexedType(GEP->getPointerOperand(), 0-th index,

  //                                      ..., i-th index).

  GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,

                                              unsigned I, Type *IndexedType);

  // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or

  // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly.

  GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,

                                              unsigned I, Value *LHS,

                                              Value *RHS, Type *IndexedType);

  // Reassociate binary operators for better CSE.

  Instruction *tryReassociateBinaryOp(BinaryOperator *I);

  // A helper function for tryReassociateBinaryOp. LHS and RHS are explicitly

  // passed.

  Instruction *tryReassociateBinaryOp(Value *LHS, Value *RHS,

                                      BinaryOperator *I);

  // Rewrites I to (LHS op RHS) if LHS is computed already.

  Instruction *tryReassociatedBinaryOp(const SCEV *LHS, Value *RHS,

                                       BinaryOperator *I);

  // Tries to match Op1 and Op2 by using V.

  bool matchTernaryOp(BinaryOperator *I, Value *V, Value *&Op1, Value *&Op2);

  // Gets SCEV for (LHS op RHS).

  const SCEV *getBinarySCEV(BinaryOperator *I, const SCEV *LHS,

                            const SCEV *RHS);

  // Returns the closest dominator of \c Dominatee that computes

  // \c CandidateExpr. Returns null if not found.

  Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,

                                            Instruction *Dominatee);

  // Try to match \p I as signed/unsigned Min/Max and reassociate it. \p

  // OrigSCEV is set if \I matches Min/Max regardless whether resassociation is

  // done or not. If reassociation was successful newly generated instruction is

  // returned, otherwise nullptr.

  template <typename PredT>

  Instruction *matchAndReassociateMinOrMax(Instruction *I,

                                           const SCEV *&OrigSCEV);

  // Reassociate Min/Max.

  template <typename MaxMinT>

  Value *tryReassociateMinOrMax(Instruction *I, MaxMinT MaxMinMatch, Value *LHS,

                                Value *RHS);

  // GetElementPtrInst implicitly sign-extends an index if the index is shorter

  // than the pointer size. This function returns whether Index is shorter than

  // GEP's pointer size, i.e., whether Index needs to be sign-extended in order

  // to be an index of GEP.

  bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);

  AssumptionCache *AC;

  const DataLayout *DL;

  DominatorTree *DT;

  ScalarEvolution *SE;

  TargetLibraryInfo *TLI;

  TargetTransformInfo *TTI;

  // A lookup table quickly telling which instructions compute the given SCEV.

  // Note that there can be multiple instructions at different locations

  // computing to the same SCEV, so we map a SCEV to an instruction list.  For

  // example,

  //

  //   if (p1)

  //     foo(a + b);

  //   if (p2)

  //     bar(a + b);

  DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs;

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H