Transforms/Scalar/Reassociate.h

0001 //===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This pass reassociates commutative expressions in an order that is designed
0010 // to promote better constant propagation, GCSE, LICM, PRE, etc.
0011 //
0012 // For example: 4 + (x + 5) -> x + (4 + 5)
0013 //
0014 // In the implementation of this algorithm, constants are assigned rank = 0,
0015 // function arguments are rank = 1, and other values are assigned ranks
0016 // corresponding to the reverse post order traversal of current function
0017 // (starting at 2), which effectively gives values in deep loops higher rank
0018 // than values not in loops.
0019 //
0020 //===----------------------------------------------------------------------===//
0021
0022 #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
0023 #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
0024
0025 #include "llvm/ADT/DenseMap.h"
0026 #include "llvm/ADT/PostOrderIterator.h"
0027 #include "llvm/ADT/SetVector.h"
0028 #include "llvm/IR/BasicBlock.h"
0029 #include "llvm/IR/PassManager.h"
0030 #include "llvm/IR/ValueHandle.h"
0031 #include <deque>
0032
0033 namespace llvm {
0034
0035 class APInt;
0036 class BasicBlock;
0037 class BinaryOperator;
0038 class Function;
0039 class Instruction;
0040 class IRBuilderBase;
0041 class Value;
0042
0043 /// A private "module" namespace for types and utilities used by Reassociate.
0044 /// These are implementation details and should not be used by clients.
0045 namespace reassociate {
0046
0047 struct ValueEntry {
0048   unsigned Rank;
0049   Value *Op;
0050
0051   ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
0052 };
0053
0054 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
0055   return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
0056 }
0057
0058 /// Utility class representing a base and exponent pair which form one
0059 /// factor of some product.
0060 struct Factor {
0061   Value *Base;
0062   unsigned Power;
0063
0064   Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
0065 };
0066
0067 struct OverflowTracking {
0068   bool HasNUW;
0069   bool HasNSW;
0070   bool AllKnownNonNegative;
0071   bool AllKnownNonZero;
0072   // Note: AllKnownNonNegative can be true in a case where one of the operands
0073   // is negative, but one the operators is not NSW. AllKnownNonNegative should
0074   // not be used independently of HasNSW
0075   OverflowTracking()
0076       : HasNUW(true), HasNSW(true), AllKnownNonNegative(true),
0077         AllKnownNonZero(true) {}
0078 };
0079
0080 class XorOpnd;
0081
0082 } // end namespace reassociate
0083
0084 /// Reassociate commutative expressions.
0085 class ReassociatePass : public PassInfoMixin<ReassociatePass> {
0086 public:
0087   using OrderedSet =
0088       SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>;
0089
0090 protected:
0091   DenseMap<BasicBlock *, unsigned> RankMap;
0092   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
0093   OrderedSet RedoInsts;
0094
0095   // Arbitrary, but prevents quadratic behavior.
0096   static const unsigned GlobalReassociateLimit = 10;
0097   static const unsigned NumBinaryOps =
0098       Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
0099
0100   struct PairMapValue {
0101     WeakVH Value1;
0102     WeakVH Value2;
0103     unsigned Score;
0104     bool isValid() const { return Value1 && Value2; }
0105   };
0106   DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps];
0107
0108   bool MadeChange;
0109
0110 public:
0111   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
0112
0113 private:
0114   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
0115   unsigned getRank(Value *V);
0116   void canonicalizeOperands(Instruction *I);
0117   void ReassociateExpression(BinaryOperator *I);
0118   void RewriteExprTree(BinaryOperator *I,
0119                        SmallVectorImpl<reassociate::ValueEntry> &Ops,
0120                        reassociate::OverflowTracking Flags);
0121   Value *OptimizeExpression(BinaryOperator *I,
0122                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
0123   Value *OptimizeAdd(Instruction *I,
0124                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
0125   Value *OptimizeXor(Instruction *I,
0126                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
0127   bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1,
0128                       APInt &ConstOpnd, Value *&Res);
0129   bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1,
0130                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
0131                       Value *&Res);
0132   Value *buildMinimalMultiplyDAG(IRBuilderBase &Builder,
0133                                  SmallVectorImpl<reassociate::Factor> &Factors);
0134   Value *OptimizeMul(BinaryOperator *I,
0135                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
0136   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
0137   void EraseInst(Instruction *I);
0138   void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts);
0139   void OptimizeInst(Instruction *I);
0140   Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op,
0141                                                Value *OtherOp);
0142   Instruction *canonicalizeNegFPConstants(Instruction *I);
0143   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
0144 };
0145
0146 } // end namespace llvm
0147
0148 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H