Reassociate.cpp

      BBI = BI;
      ++BBI;
      MadeChange = true;
    } else if (BinaryOperator::isNeg(BI)) {
      // Otherwise, this is a negation.  See if the operand is a multiply tree
      // and if this is not an inner node of a multiply tree.
      if (isReassociableOp(BI->getOperand(1), Instruction::Mul) &&
          (!BI->hasOneUse() ||
           !isReassociableOp(BI->use_back(), Instruction::Mul))) {
        BI = LowerNegateToMultiply(BI, ValueRankMap);
        MadeChange = true;
      }
    }
  }

  // If this instruction is a commutative binary operator, process it.
  if (!BI->isAssociative()) return;
  BinaryOperator *I = cast<BinaryOperator>(BI);

  // If this is an interior node of a reassociable tree, ignore it until we
  // get to the root of the tree, to avoid N^2 analysis.
  if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
    return;

  // If this is an add tree that is used by a sub instruction, ignore it 
  // until we process the subtract.
  if (I->hasOneUse() && I->getOpcode() == Instruction::Add &&
      cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub)
    return;

  ReassociateExpression(I);
}

Value *Reassociate::ReassociateExpression(BinaryOperator *I) {
  
  // First, walk the expression tree, linearizing the tree, collecting the
  // operand information.
  SmallVector<ValueEntry, 8> Ops;
  LinearizeExprTree(I, Ops);
  
  DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
  
  // Now that we have linearized the tree to a list and have gathered all of
  // the operands and their ranks, sort the operands by their rank.  Use a
  // stable_sort so that values with equal ranks will have their relative
  // positions maintained (and so the compiler is deterministic).  Note that
  // this sorts so that the highest ranking values end up at the beginning of
  // the vector.
  std::stable_sort(Ops.begin(), Ops.end());
  
  // OptimizeExpression - Now that we have the expression tree in a convenient
  // sorted form, optimize it globally if possible.
  if (Value *V = OptimizeExpression(I, Ops)) {
    // This expression tree simplified to something that isn't a tree,
    // eliminate it.
    DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
    I->replaceAllUsesWith(V);
    if (Instruction *VI = dyn_cast<Instruction>(V))
      VI->setDebugLoc(I->getDebugLoc());
    RemoveDeadBinaryOp(I);
    ++NumAnnihil;
    return V;
  }
  
  // We want to sink immediates as deeply as possible except in the case where
  // this is a multiply tree used only by an add, and the immediate is a -1.
  // In this case we reassociate to put the negation on the outside so that we
  // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
  if (I->getOpcode() == Instruction::Mul && I->hasOneUse() &&
      cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add &&
      isa<ConstantInt>(Ops.back().Op) &&
      cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) {
    ValueEntry Tmp = Ops.pop_back_val();
    Ops.insert(Ops.begin(), Tmp);
  }
  
  DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
  
  if (Ops.size() == 1) {
    // This expression tree simplified to something that isn't a tree,
    // eliminate it.
    I->replaceAllUsesWith(Ops[0].Op);
    if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
      OI->setDebugLoc(I->getDebugLoc());
    RemoveDeadBinaryOp(I);
    return Ops[0].Op;
  }
  
  // Now that we ordered and optimized the expressions, splat them back into
  // the expression tree, removing any unneeded nodes.
  RewriteExprTree(I, Ops);
  return I;
}


bool Reassociate::runOnFunction(Function &F) {
  // Recalculate the rank map for F
  BuildRankMap(F);

  MadeChange = false;
  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
    for (BasicBlock::iterator BBI = FI->begin(); BBI != FI->end(); )
      ReassociateInst(BBI);

  // Now that we're done, revisit any instructions which are likely to
  // have secondary reassociation opportunities.
  while (!RedoInsts.empty())
    if (Value *V = RedoInsts.pop_back_val()) {
      BasicBlock::iterator BBI = cast<Instruction>(V);
      ReassociateInst(BBI);
    }

  // Now that we're done, delete any instructions which are no longer used.
  while (!DeadInsts.empty())
    if (Value *V = DeadInsts.pop_back_val())
      RecursivelyDeleteTriviallyDeadInstructions(V);

  // We are done with the rank map.
  RankMap.clear();
  ValueRankMap.clear();
  return MadeChange;
}