SCCP.cpp

// createSCCPPass - This is the public interface to this file...
FunctionPass *llvm::createSCCPPass() {
  return new SCCP();
}


// runOnFunction() - Run the Sparse Conditional Constant Propagation algorithm,
// and return true if the function was modified.
//
bool SCCP::runOnFunction(Function &F) {
  DEBUG(std::cerr << "SCCP on function '" << F.getName() << "'\n");
  SCCPSolver Solver;

  // Mark the first block of the function as being executable.
  Solver.MarkBlockExecutable(F.begin());

  // Mark all arguments to the function as being overdefined.
  hash_map<Value*, LatticeVal> &Values = Solver.getValueMapping();
  for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E; ++AI)
    Values[AI].markOverdefined();

  // Solve for constants.
  bool ResolvedBranches = true;
  while (ResolvedBranches) {
    Solver.Solve();
    DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
    ResolvedBranches = Solver.ResolveBranchesIn(F);
  }

  bool MadeChanges = false;

  // If we decided that there are basic blocks that are dead in this function,
  // delete their contents now.  Note that we cannot actually delete the blocks,
  // as we cannot modify the CFG of the function.
  //
  std::set<BasicBlock*> &ExecutableBBs = Solver.getExecutableBlocks();
  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    if (!ExecutableBBs.count(BB)) {
      DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
      ++NumDeadBlocks;

      // 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;
      for (BasicBlock::iterator I = BB->begin(), E = BB->getTerminator();
           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;
        ++NumInstRemoved;
      }
    } else {
      // Iterate over all of the instructions in a function, replacing them with
      // constants if we have found them to be of constant values.
      //
      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.
            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");
  Statistic<> IPNumGlobalConst("ipsccp",
                               "Number of globals found to be constant");

  //===--------------------------------------------------------------------===//
  //
  /// 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) {
  // Delete any dead constantexpr klingons.
  GV->removeDeadConstantUsers();

  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 || SI->isVolatile())
        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 (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
      if (LI->isVolatile())
        return true;
    } else {
      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::arg_iterator AI = F->arg_begin(), E = F->arg_end();
           AI != E; ++AI)
        Values[AI].markOverdefined();
    } else {
      Solver.AddTrackedFunction(F);
    }

  // Loop over global variables.  We inform the solver about any internal global
  // variables that do not have their 'addresses taken'.  If they don't have
  // their addresses taken, we can propagate constants through them.
  for (Module::global_iterator G = M.global_begin(), E = M.global_end();
       G != E; ++G)
    if (!G->isConstant() && G->hasInternalLinkage() && !AddressIsTaken(G))
      Solver.TrackValueOfGlobalVariable(G);

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

    DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
    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::arg_iterator AI = F->arg_begin(), E = F->arg_end();
         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;

        // 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);
        }
        if (!TI->use_empty())
          TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
        BB->getInstList().erase(TI);

        if (&*BB != &F->front())
          BlocksToErase.push_back(BB);
        else
          new UnreachableInst(BB);

      } 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);
    }
  }

  // If we inferred constant or undef return values for a function, we replaced
  // all call uses with the inferred value.  This means we don't need to bother
  // actually returning anything from the function.  Replace all return
  // instructions with return undef.
  const hash_map<Function*, LatticeVal> &RV =Solver.getTrackedFunctionRetVals();
  for (hash_map<Function*, LatticeVal>::const_iterator I = RV.begin(),
         E = RV.end(); I != E; ++I)
    if (!I->second.isOverdefined() &&
        I->first->getReturnType() != Type::VoidTy) {
      Function *F = I->first;
      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
        if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
          if (!isa<UndefValue>(RI->getOperand(0)))
            RI->setOperand(0, UndefValue::get(F->getReturnType()));
    }

  // If we infered constant or undef values for globals variables, we can delete
  // the global and any stores that remain to it.
  const hash_map<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
  for (hash_map<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
         E = TG.end(); I != E; ++I) {
    GlobalVariable *GV = I->first;
    assert(!I->second.isOverdefined() &&
           "Overdefined values should have been taken out of the map!");
    DEBUG(std::cerr << "Found that GV '" << GV->getName()<< "' is constant!\n");
    while (!GV->use_empty()) {
      StoreInst *SI = cast<StoreInst>(GV->use_back());
      SI->eraseFromParent();
    }
    M.getGlobalList().erase(GV);
    ++IPNumGlobalConst;
  }

  return MadeChanges;
}