/// MarkValue - This function marks the liveness of RA depending on L. If L is
/// MaybeLive, it also takes all uses in MaybeLiveUses and records them in Uses,
/// such that RA will be marked live if any use in MaybeLiveUses gets marked
/// live later on.
void DAE::MarkValue(const RetOrArg &RA, Liveness L,
                    const UseVector &MaybeLiveUses) {
  switch (L) {
    case Live: MarkLive(RA); break;
    case MaybeLive:
    {
      // Note any uses of this value, so this return value can be
      // marked live whenever one of the uses becomes live.
      for (UseVector::const_iterator UI = MaybeLiveUses.begin(),
           UE = MaybeLiveUses.end(); UI != UE; ++UI)
        Uses.insert(std::make_pair(*UI, RA));
      break;
    }
  }
}

static void vectorExample() {
	UseVector *vector = new UseVector();
	Shape *circle = UseFactory::makeShape(UseEnumeration::e_shape::Circle);
	circle->setRadius(3);
	vector->pushBackVector(circle);
	Shape *rectangle = UseFactory::makeShape(UseEnumeration::e_shape::Rectangle);
	rectangle->setHeight(3);
	rectangle->setWidth(4);
	vector->pushBackVector(rectangle);
	Shape *triangle = UseFactory::makeShape(UseEnumeration::e_shape::Triangle);
	triangle->setHeight(3);
	triangle->setWidth(4);
	vector->pushBackVector(triangle);

	vector->printVector();
	delete vector;
}

/// MarkIfNotLive - This checks Use for liveness in LiveValues. If Use is not
/// live, it adds Use to the MaybeLiveUses argument. Returns the determined
/// liveness of Use.
DAE::Liveness DAE::MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses) {
  // We're live if our use or its Function is already marked as live.
  if (LiveFunctions.count(Use.F) || LiveValues.count(Use))
    return Live;

  // We're maybe live otherwise, but remember that we must become live if
  // Use becomes live.
  MaybeLiveUses.push_back(Use);
  return MaybeLive;
}

// SurveyFunction - This performs the initial survey of the specified function,
// checking out whether or not it uses any of its incoming arguments or whether
// any callers use the return value.  This fills in the LiveValues set and Uses
// map.
//
// We consider arguments of non-internal functions to be intrinsically alive as
// well as arguments to functions which have their "address taken".
//
void DAE::SurveyFunction(const Function &F) {
  // Functions with inalloca parameters are expecting args in a particular
  // register and memory layout.
  if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca)) {
    MarkLive(F);
    return;
  }

  // Don't touch naked functions. The assembly might be using an argument, or
  // otherwise rely on the frame layout in a way that this analysis will not
  // see.
  if (F.hasFnAttribute(Attribute::Naked)) {
    MarkLive(F);
    return;
  }

  unsigned RetCount = NumRetVals(&F);
  // Assume all return values are dead
  typedef SmallVector<Liveness, 5> RetVals;
  RetVals RetValLiveness(RetCount, MaybeLive);

  typedef SmallVector<UseVector, 5> RetUses;
  // These vectors map each return value to the uses that make it MaybeLive, so
  // we can add those to the Uses map if the return value really turns out to be
  // MaybeLive. Initialized to a list of RetCount empty lists.
  RetUses MaybeLiveRetUses(RetCount);

  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
      if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
          != F.getFunctionType()->getReturnType()) {
        // We don't support old style multiple return values.
        MarkLive(F);
        return;
      }

  if (!F.hasLocalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) {
    MarkLive(F);
    return;
  }

  DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n");
  // Keep track of the number of live retvals, so we can skip checks once all
  // of them turn out to be live.
  unsigned NumLiveRetVals = 0;
  // Loop all uses of the function.
  for (const Use &U : F.uses()) {
    // If the function is PASSED IN as an argument, its address has been
    // taken.
    ImmutableCallSite CS(U.getUser());
    if (!CS || !CS.isCallee(&U)) {
      MarkLive(F);
      return;
    }

    // If this use is anything other than a call site, the function is alive.
    const Instruction *TheCall = CS.getInstruction();
    if (!TheCall) {   // Not a direct call site?
      MarkLive(F);
      return;
    }

    // If we end up here, we are looking at a direct call to our function.

    // Now, check how our return value(s) is/are used in this caller. Don't
    // bother checking return values if all of them are live already.
    if (NumLiveRetVals == RetCount)
      continue;

    // Check all uses of the return value.
    for (const Use &U : TheCall->uses()) {
      if (ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(U.getUser())) {
        // This use uses a part of our return value, survey the uses of
        // that part and store the results for this index only.
        unsigned Idx = *Ext->idx_begin();
        if (RetValLiveness[Idx] != Live) {
          RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
          if (RetValLiveness[Idx] == Live)
            NumLiveRetVals++;
        }
      } else {
        // Used by something else than extractvalue. Survey, but assume that the
        // result applies to all sub-values.
        UseVector MaybeLiveAggregateUses;
        if (SurveyUse(&U, MaybeLiveAggregateUses) == Live) {
          NumLiveRetVals = RetCount;
          RetValLiveness.assign(RetCount, Live);
          break;
        } else {
          for (unsigned i = 0; i != RetCount; ++i) {
            if (RetValLiveness[i] != Live)
              MaybeLiveRetUses[i].append(MaybeLiveAggregateUses.begin(),
//.........这里部分代码省略.........

// SurveyFunction - This performs the initial survey of the specified function,
// checking out whether or not it uses any of its incoming arguments or whether
// any callers use the return value.  This fills in the LiveValues set and Uses
// map.
//
// We consider arguments of non-internal functions to be intrinsically alive as
// well as arguments to functions which have their "address taken".
//
void DAE::SurveyFunction(const Function &F) {
  unsigned RetCount = NumRetVals(&F);
  // Assume all return values are dead
  typedef SmallVector<Liveness, 5> RetVals;
  RetVals RetValLiveness(RetCount, MaybeLive);

  typedef SmallVector<UseVector, 5> RetUses;
  // These vectors map each return value to the uses that make it MaybeLive, so
  // we can add those to the Uses map if the return value really turns out to be
  // MaybeLive. Initialized to a list of RetCount empty lists.
  RetUses MaybeLiveRetUses(RetCount);

  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
    if (const ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()))
      if (RI->getNumOperands() != 0 && RI->getOperand(0)->getType()
          != F.getFunctionType()->getReturnType()) {
        // We don't support old style multiple return values.
        MarkLive(F);
        return;
      }

  if (!F.hasLocalLinkage() && (!ShouldHackArguments() || F.isIntrinsic())) {
    MarkLive(F);
    return;
  }

  DEBUG(dbgs() << "DAE - Inspecting callers for fn: " << F.getName() << "\n");
  // Keep track of the number of live retvals, so we can skip checks once all
  // of them turn out to be live.
  unsigned NumLiveRetVals = 0;
  Type *STy = dyn_cast<StructType>(F.getReturnType());
  // Loop all uses of the function.
  for (Value::const_use_iterator I = F.use_begin(), E = F.use_end();
       I != E; ++I) {
    // If the function is PASSED IN as an argument, its address has been
    // taken.
    ImmutableCallSite CS(*I);
    if (!CS || !CS.isCallee(I)) {
      MarkLive(F);
      return;
    }

    // If this use is anything other than a call site, the function is alive.
    const Instruction *TheCall = CS.getInstruction();
    if (!TheCall) {   // Not a direct call site?
      MarkLive(F);
      return;
    }

    // If we end up here, we are looking at a direct call to our function.

    // Now, check how our return value(s) is/are used in this caller. Don't
    // bother checking return values if all of them are live already.
    if (NumLiveRetVals != RetCount) {
      if (STy) {
        // Check all uses of the return value.
        for (Value::const_use_iterator I = TheCall->use_begin(),
             E = TheCall->use_end(); I != E; ++I) {
          const ExtractValueInst *Ext = dyn_cast<ExtractValueInst>(*I);
          if (Ext && Ext->hasIndices()) {
            // This use uses a part of our return value, survey the uses of
            // that part and store the results for this index only.
            unsigned Idx = *Ext->idx_begin();
            if (RetValLiveness[Idx] != Live) {
              RetValLiveness[Idx] = SurveyUses(Ext, MaybeLiveRetUses[Idx]);
              if (RetValLiveness[Idx] == Live)
                NumLiveRetVals++;
            }
          } else {
            // Used by something else than extractvalue. Mark all return
            // values as live.
            for (unsigned i = 0; i != RetCount; ++i )
              RetValLiveness[i] = Live;
            NumLiveRetVals = RetCount;
            break;
          }
        }
      } else {
        // Single return value
        RetValLiveness[0] = SurveyUses(TheCall, MaybeLiveRetUses[0]);
        if (RetValLiveness[0] == Live)
          NumLiveRetVals = RetCount;
      }
    }
  }

  // Now we've inspected all callers, record the liveness of our return values.
  for (unsigned i = 0; i != RetCount; ++i)
    MarkValue(CreateRet(&F, i), RetValLiveness[i], MaybeLiveRetUses[i]);

  DEBUG(dbgs() << "DAE - Inspecting args for fn: " << F.getName() << "\n");

//.........这里部分代码省略.........