Reassociate.h revision 327952 
1//===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass reassociates commutative expressions in an order that is designed
11// to promote better constant propagation, GCSE, LICM, PRE, etc.
12//
13// For example: 4 + (x + 5) -> x + (4 + 5)
14//
15// In the implementation of this algorithm, constants are assigned rank = 0,
16// function arguments are rank = 1, and other values are assigned ranks
17// corresponding to the reverse post order traversal of current function
18// (starting at 2), which effectively gives values in deep loops higher rank
19// than values not in loops.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
24#define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
25
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/PostOrderIterator.h"
28#include "llvm/ADT/SetVector.h"
29#include "llvm/IR/IRBuilder.h"
30#include "llvm/IR/PassManager.h"
31#include "llvm/IR/ValueHandle.h"
32
33namespace llvm {
34
35class APInt;
36class BasicBlock;
37class BinaryOperator;
38class Function;
39class Instruction;
40class Value;
41
42/// A private "module" namespace for types and utilities used by Reassociate.
43/// These are implementation details and should not be used by clients.
44namespace reassociate {
45
46struct ValueEntry {
47  unsigned Rank;
48  Value *Op;
49
50  ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
51};
52
53inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
54  return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
55}
56
57/// \brief Utility class representing a base and exponent pair which form one
58/// factor of some product.
59struct Factor {
60  Value *Base;
61  unsigned Power;
62
63  Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
64};
65
66class XorOpnd;
67
68} // end namespace reassociate
69
70/// Reassociate commutative expressions.
71class ReassociatePass : public PassInfoMixin<ReassociatePass> {
72  DenseMap<BasicBlock *, unsigned> RankMap;
73  DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
74  SetVector<AssertingVH<Instruction>> RedoInsts;
75
76  // Arbitrary, but prevents quadratic behavior.
77  static const unsigned GlobalReassociateLimit = 10;
78  static const unsigned NumBinaryOps =
79      Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
80  DenseMap<std::pair<Value *, Value *>, unsigned> PairMap[NumBinaryOps];
81
82  bool MadeChange;
83
84public:
85  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
86
87private:
88  void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
89  unsigned getRank(Value *V);
90  void canonicalizeOperands(Instruction *I);
91  void ReassociateExpression(BinaryOperator *I);
92  void RewriteExprTree(BinaryOperator *I,
93                       SmallVectorImpl<reassociate::ValueEntry> &Ops);
94  Value *OptimizeExpression(BinaryOperator *I,
95                            SmallVectorImpl<reassociate::ValueEntry> &Ops);
96  Value *OptimizeAdd(Instruction *I,
97                     SmallVectorImpl<reassociate::ValueEntry> &Ops);
98  Value *OptimizeXor(Instruction *I,
99                     SmallVectorImpl<reassociate::ValueEntry> &Ops);
100  bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
101                      APInt &ConstOpnd, Value *&Res);
102  bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
103                      reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
104                      Value *&Res);
105  Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
106                                 SmallVectorImpl<reassociate::Factor> &Factors);
107  Value *OptimizeMul(BinaryOperator *I,
108                     SmallVectorImpl<reassociate::ValueEntry> &Ops);
109  Value *RemoveFactorFromExpression(Value *V, Value *Factor);
110  void EraseInst(Instruction *I);
111  void RecursivelyEraseDeadInsts(Instruction *I,
112                                 SetVector<AssertingVH<Instruction>> &Insts);
113  void OptimizeInst(Instruction *I);
114  Instruction *canonicalizeNegConstExpr(Instruction *I);
115  void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
116};
117
118} // end namespace llvm
119
120#endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
121