SCCP.cpp

            DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
            
            // Replaces all of the uses of a variable with uses of the constant.
            Inst->replaceAllUsesWith(Const);
            
            // Delete the instruction.
            BB->getInstList().erase(Inst);
            
            // Hey, we just changed something!
            MadeChanges = true;
            ++NumInstRemoved;
          }
        }
      }
    }

  return MadeChanges;
}

namespace {
  Statistic<> IPNumInstRemoved("ipsccp", "Number of instructions removed");
  Statistic<> IPNumDeadBlocks ("ipsccp", "Number of basic blocks unreachable");
  Statistic<> IPNumArgsElimed ("ipsccp",
                               "Number of arguments constant propagated");

  //===--------------------------------------------------------------------===//
  //
  /// IPSCCP Class - This class implements interprocedural Sparse Conditional
  /// Constant Propagation.
  ///
  struct IPSCCP : public ModulePass {
    bool runOnModule(Module &M);
  };

  RegisterOpt<IPSCCP>
  Y("ipsccp", "Interprocedural Sparse Conditional Constant Propagation");
} // end anonymous namespace

// createIPSCCPPass - This is the public interface to this file...
ModulePass *llvm::createIPSCCPPass() {
  return new IPSCCP();
}


static bool AddressIsTaken(GlobalValue *GV) {
  for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
       UI != E; ++UI)
    if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
      if (SI->getOperand(0) == GV) return true;  // Storing addr of GV.
    } else if (isa<InvokeInst>(*UI) || isa<CallInst>(*UI)) {
      // Make sure we are calling the function, not passing the address.
      CallSite CS = CallSite::get(cast<Instruction>(*UI));
      for (CallSite::arg_iterator AI = CS.arg_begin(),
             E = CS.arg_end(); AI != E; ++AI)
        if (*AI == GV)
          return true;
    } else if (!isa<LoadInst>(*UI)) {
      return true;
    }
  return false;
}

bool IPSCCP::runOnModule(Module &M) {
  SCCPSolver Solver;

  // Loop over all functions, marking arguments to those with their addresses
  // taken or that are external as overdefined.
  //
  hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
    if (!F->hasInternalLinkage() || AddressIsTaken(F)) {
      if (!F->isExternal())
        Solver.MarkBlockExecutable(F->begin());
      for (Function::aiterator AI = F->abegin(), E = F->aend(); AI != E; ++AI)
        Values[AI].markOverdefined();
    } else {
      Solver.AddTrackedFunction(F);
    }

  // Solve for constants.
  bool ResolvedBranches = true;
  while (ResolvedBranches) {
    Solver.Solve();

    ResolvedBranches = false;
    for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
      ResolvedBranches |= Solver.ResolveBranchesIn(*F);
  }

  bool MadeChanges = false;

  // Iterate over all of the instructions in the module, replacing them with
  // constants if we have found them to be of constant values.
  //
  std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
    for (Function::aiterator AI = F->abegin(), E = F->aend(); AI != E; ++AI)
      if (!AI->use_empty()) {
        LatticeVal &IV = Values[AI];
        if (IV.isConstant() || IV.isUndefined()) {
          Constant *CST = IV.isConstant() ?
            IV.getConstant() : UndefValue::get(AI->getType());
          DEBUG(std::cerr << "***  Arg " << *AI << " = " << *CST <<"\n");
          
          // Replaces all of the uses of a variable with uses of the
          // constant.
          AI->replaceAllUsesWith(CST);
          ++IPNumArgsElimed;
        }
      }

    std::vector<BasicBlock*> BlocksToErase;
    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
      if (!ExecutableBBs.count(BB)) {
        DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
        ++IPNumDeadBlocks;
        BlocksToErase.push_back(BB);

        // Delete the instructions backwards, as it has a reduced likelihood of
        // having to update as many def-use and use-def chains.
        std::vector<Instruction*> Insts;
        TerminatorInst *TI = BB->getTerminator();
        for (BasicBlock::iterator I = BB->begin(), E = TI; I != E; ++I)
          Insts.push_back(I);

        while (!Insts.empty()) {
          Instruction *I = Insts.back();
          Insts.pop_back();
          if (!I->use_empty())
            I->replaceAllUsesWith(UndefValue::get(I->getType()));
          BB->getInstList().erase(I);
          MadeChanges = true;
          ++IPNumInstRemoved;
        }
        
        for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
          BasicBlock *Succ = TI->getSuccessor(i);
          if (Succ->begin() != Succ->end() && isa<PHINode>(Succ->begin()))
            TI->getSuccessor(i)->removePredecessor(BB);
        }
        BB->getInstList().erase(TI);

      } else {
        for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
          Instruction *Inst = BI++;
          if (Inst->getType() != Type::VoidTy) {
            LatticeVal &IV = Values[Inst];
            if (IV.isConstant() || IV.isUndefined() &&
                !isa<TerminatorInst>(Inst)) {
              Constant *Const = IV.isConstant()
                ? IV.getConstant() : UndefValue::get(Inst->getType());
              DEBUG(std::cerr << "  Constant: " << *Const << " = " << *Inst);
              
              // Replaces all of the uses of a variable with uses of the
              // constant.
              Inst->replaceAllUsesWith(Const);
              
              // Delete the instruction.
              if (!isa<TerminatorInst>(Inst) && !isa<CallInst>(Inst))
                BB->getInstList().erase(Inst);

              // Hey, we just changed something!
              MadeChanges = true;
              ++IPNumInstRemoved;
            }
          }
        }
      }

    // Now that all instructions in the function are constant folded, erase dead
    // blocks, because we can now use ConstantFoldTerminator to get rid of
    // in-edges.
    for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
      // If there are any PHI nodes in this successor, drop entries for BB now.
      BasicBlock *DeadBB = BlocksToErase[i];
      while (!DeadBB->use_empty()) {
        Instruction *I = cast<Instruction>(DeadBB->use_back());
        bool Folded = ConstantFoldTerminator(I->getParent());
        assert(Folded && "Didn't fold away reference to block!");
      }
        
      // Finally, delete the basic block.
      F->getBasicBlockList().erase(DeadBB);
    }
  }
  return MadeChanges;
}