lib/Transforms/Scalar/Reassociate.cpp

   1 //===- Reassociate.cpp - Reassociate binary expressions -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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...
  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 #define DEBUG_TYPE "reassociate"
  24 #include "llvm/Transforms/Scalar.h"
  25 #include "llvm/Function.h"
  26 #include "llvm/Instructions.h"
  27 #include "llvm/Type.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/Constant.h"
  30 #include "llvm/Support/CFG.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/ADT/PostOrderIterator.h"
  33 #include "llvm/ADT/Statistic.h"
  34 using namespace llvm;
  35
  36 namespace {
  37   Statistic<> NumLinear ("reassociate","Number of insts linearized");
  38   Statistic<> NumChanged("reassociate","Number of insts reassociated");
  39   Statistic<> NumSwapped("reassociate","Number of insts with operands swapped");
  40
  41   class Reassociate : public FunctionPass {
  42     std::map<BasicBlock*, unsigned> RankMap;
  43     std::map<Value*, unsigned> ValueRankMap;
  44   public:
  45     bool runOnFunction(Function &F);
  46
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.setPreservesCFG();
  49     }
  50   private:
  51     void BuildRankMap(Function &F);
  52     unsigned getRank(Value *V);
  53     bool ReassociateExpr(BinaryOperator *I);
  54     bool ReassociateBB(BasicBlock *BB);
  55   };
  56
  57   RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions");
  58 }
  59
  60 // Public interface to the Reassociate pass
  61 FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
  62
  63 void Reassociate::BuildRankMap(Function &F) {
  64   unsigned i = 2;
  65
  66   // Assign distinct ranks to function arguments
  67   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
  68     ValueRankMap[I] = ++i;
  69
  70   ReversePostOrderTraversal<Function*> RPOT(&F);
  71   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
  72          E = RPOT.end(); I != E; ++I)
  73     RankMap[*I] = ++i << 16;
  74 }
  75
  76 unsigned Reassociate::getRank(Value *V) {
  77   if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument...
  78
  79   Instruction *I = dyn_cast<Instruction>(V);
  80   if (I == 0) return 0;  // Otherwise it's a global or constant, rank 0.
  81
  82   unsigned &CachedRank = ValueRankMap[I];
  83   if (CachedRank) return CachedRank;    // Rank already known?
  84
  85   // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that
  86   // we can reassociate expressions for code motion!  Since we do not recurse
  87   // for PHI nodes, we cannot have infinite recursion here, because there
  88   // cannot be loops in the value graph that do not go through PHI nodes.
  89   //
  90   if (I->getOpcode() == Instruction::PHI ||
  91       I->getOpcode() == Instruction::Alloca ||
  92       I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) ||
  93       I->mayWriteToMemory())  // Cannot move inst if it writes to memory!
  94     return RankMap[I->getParent()];
  95
  96   // If not, compute it!
  97   unsigned Rank = 0, MaxRank = RankMap[I->getParent()];
  98   for (unsigned i = 0, e = I->getNumOperands();
  99        i != e && Rank != MaxRank; ++i)
 100     Rank = std::max(Rank, getRank(I->getOperand(i)));
 101
 102   DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = "
 103         << Rank+1 << "\n");
 104
 105   return CachedRank = Rank+1;
 106 }
 107
 108
 109 bool Reassociate::ReassociateExpr(BinaryOperator *I) {
 110   Value *LHS = I->getOperand(0);
 111   Value *RHS = I->getOperand(1);
 112   unsigned LHSRank = getRank(LHS);
 113   unsigned RHSRank = getRank(RHS);
 114
 115   bool Changed = false;
 116
 117   // Make sure the LHS of the operand always has the greater rank...
 118   if (LHSRank < RHSRank) {
 119     bool Success = !I->swapOperands();
 120     assert(Success && "swapOperands failed");
 121
 122     std::swap(LHS, RHS);
 123     std::swap(LHSRank, RHSRank);
 124     Changed = true;
 125     ++NumSwapped;
 126     DEBUG(std::cerr << "Transposed: " << *I
 127           /* << " Result BB: " << I->getParent()*/);
 128   }
 129
 130   // If the LHS is the same operator as the current one is, and if we are the
 131   // only expression using it...
 132   //
 133   if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS))
 134     if (LHSI->getOpcode() == I->getOpcode() && LHSI->hasOneUse()) {
 135       // If the rank of our current RHS is less than the rank of the LHS's LHS,
 136       // then we reassociate the two instructions...
 137
 138       unsigned TakeOp = 0;
 139       if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0)))
 140         if (IOp->getOpcode() == LHSI->getOpcode())
 141           TakeOp = 1;   // Hoist out non-tree portion
 142
 143       if (RHSRank < getRank(LHSI->getOperand(TakeOp))) {
 144         // Convert ((a + 12) + 10) into (a + (12 + 10))
 145         I->setOperand(0, LHSI->getOperand(TakeOp));
 146         LHSI->setOperand(TakeOp, RHS);
 147         I->setOperand(1, LHSI);
 148
 149         // Move the LHS expression forward, to ensure that it is dominated by
 150         // its operands.
 151         LHSI->getParent()->getInstList().remove(LHSI);
 152         I->getParent()->getInstList().insert(I, LHSI);
 153
 154         ++NumChanged;
 155         DEBUG(std::cerr << "Reassociated: " << *I/* << " Result BB: "
 156                                                    << I->getParent()*/);
 157
 158         // Since we modified the RHS instruction, make sure that we recheck it.
 159         ReassociateExpr(LHSI);
 160         ReassociateExpr(I);
 161         return true;
 162       }
 163     }
 164
 165   return Changed;
 166 }
 167
 168
 169 // NegateValue - Insert instructions before the instruction pointed to by BI,
 170 // that computes the negative version of the value specified.  The negative
 171 // version of the value is returned, and BI is left pointing at the instruction
 172 // that should be processed next by the reassociation pass.
 173 //
 174 static Value *NegateValue(Value *V, Instruction *BI) {
 175   // We are trying to expose opportunity for reassociation.  One of the things
 176   // that we want to do to achieve this is to push a negation as deep into an
 177   // expression chain as possible, to expose the add instructions.  In practice,
 178   // this means that we turn this:
 179   //   X = -(A+12+C+D)   into    X = -A + -12 + -C + -D = -12 + -A + -C + -D
 180   // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate
 181   // the constants.  We assume that instcombine will clean up the mess later if
 182   // we introduce tons of unnecessary negation instructions...
 183   //
 184   if (Instruction *I = dyn_cast<Instruction>(V))
 185     if (I->getOpcode() == Instruction::Add && I->hasOneUse()) {
 186       Value *RHS = NegateValue(I->getOperand(1), BI);
 187       Value *LHS = NegateValue(I->getOperand(0), BI);
 188
 189       // We must actually insert a new add instruction here, because the neg
 190       // instructions do not dominate the old add instruction in general.  By
 191       // adding it now, we are assured that the neg instructions we just
 192       // inserted dominate the instruction we are about to insert after them.
 193       //
 194       return BinaryOperator::create(Instruction::Add, LHS, RHS,
 195                                     I->getName()+".neg", BI);
 196     }
 197
 198   // Insert a 'neg' instruction that subtracts the value from zero to get the
 199   // negation.
 200   //
 201   return BinaryOperator::createNeg(V, V->getName() + ".neg", BI);
 202 }
 203
 204 /// isReassociableOp - Return true if V is an instruction of the specified
 205 /// opcode and if it only has one use.
 206 static bool isReassociableOp(Value *V, unsigned Opcode) {
 207   return V->hasOneUse() && isa<Instruction>(V) &&
 208          cast<Instruction>(V)->getOpcode() == Opcode;
 209 }
 210
 211 /// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is
 212 /// only used by an add, transform this into (X+(0-Y)) to promote better
 213 /// reassociation.
 214 static Instruction *BreakUpSubtract(Instruction *Sub) {
 215   // Reject cases where it is pointless to do this.
 216   if (Sub->getType()->isFloatingPoint())
 217     return 0;  // Floating point adds are not associative.
 218
 219   // Don't bother to break this up unless either the LHS is an associable add or
 220   // if this is only used by one.
 221   if (!isReassociableOp(Sub->getOperand(0), Instruction::Add) &&
 222       !isReassociableOp(Sub->getOperand(1), Instruction::Add) &&
 223       !(Sub->hasOneUse() &&isReassociableOp(Sub->use_back(), Instruction::Add)))
 224     return 0;
 225
 226   // Convert a subtract into an add and a neg instruction... so that sub
 227   // instructions can be commuted with other add instructions...
 228   //
 229   // Calculate the negative value of Operand 1 of the sub instruction...
 230   // and set it as the RHS of the add instruction we just made...
 231   //
 232   std::string Name = Sub->getName();
 233   Sub->setName("");
 234   Value *NegVal = NegateValue(Sub->getOperand(1), Sub);
 235   Instruction *New =
 236     BinaryOperator::createAdd(Sub->getOperand(0), NegVal, Name, Sub);
 237
 238   // Everyone now refers to the add instruction.
 239   Sub->replaceAllUsesWith(New);
 240   Sub->eraseFromParent();
 241
 242   DEBUG(std::cerr << "Negated: " << *New);
 243   return New;
 244 }
 245
 246
 247 /// ReassociateBB - Inspect all of the instructions in this basic block,
 248 /// reassociating them as we go.
 249 bool Reassociate::ReassociateBB(BasicBlock *BB) {
 250   bool Changed = false;
 251   for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) {
 252     // If this is a subtract instruction which is not already in negate form,
 253     // see if we can convert it to X+-Y.
 254     if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI))
 255       if (Instruction *NI = BreakUpSubtract(BI)) {
 256         Changed = true;
 257         BI = NI;
 258       }
 259
 260     // If this instruction is a commutative binary operator, and the ranks of
 261     // the two operands are sorted incorrectly, fix it now.
 262     //
 263     if (BI->isAssociative()) {
 264       DEBUG(std::cerr << "Reassociating: " << *BI);
 265       BinaryOperator *I = cast<BinaryOperator>(BI);
 266       if (!I->use_empty()) {
 267         // Make sure that we don't have a tree-shaped computation.  If we do,
 268         // linearize it.  Convert (A+B)+(C+D) into ((A+B)+C)+D
 269         //
 270         Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0));
 271         Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1));
 272         if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() &&
 273             RHSI && (int)RHSI->getOpcode() == I->getOpcode() &&
 274             RHSI->hasOneUse()) {
 275           // Insert a new temporary instruction... (A+B)+C
 276           BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI,
 277                                                        RHSI->getOperand(0),
 278                                                        RHSI->getName()+".ra",
 279                                                        BI);
 280           BI = Tmp;
 281           I->setOperand(0, Tmp);
 282           I->setOperand(1, RHSI->getOperand(1));
 283
 284           // Process the temporary instruction for reassociation now.
 285           I = Tmp;
 286           ++NumLinear;
 287           Changed = true;
 288           DEBUG(std::cerr << "Linearized: " << *I/* << " Result BB: " << BB*/);
 289         }
 290
 291         // Make sure that this expression is correctly reassociated with respect
 292         // to it's used values...
 293         //
 294         Changed |= ReassociateExpr(I);
 295       }
 296     }
 297   }
 298
 299   return Changed;
 300 }
 301
 302
 303 bool Reassociate::runOnFunction(Function &F) {
 304   // Recalculate the rank map for F
 305   BuildRankMap(F);
 306
 307   bool Changed = false;
 308   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
 309     Changed |= ReassociateBB(FI);
 310
 311   // We are done with the rank map...
 312   RankMap.clear();
 313   ValueRankMap.clear();
 314   return Changed;
 315 }
 316