MachineInstr.cpp

  if (TID->mayStore() || TID->isCall()) {
    SawStore = true;
    return false;
  }
  if (TID->isTerminator() || TID->hasUnmodeledSideEffects())
    return false;

  // See if this instruction does a load.  If so, we have to guarantee that the
  // loaded value doesn't change between the load and the its intended
  // destination. The check for isInvariantLoad gives the targe the chance to
  // classify the load as always returning a constant, e.g. a constant pool
  // load.
  if (TID->mayLoad() && !isInvariantLoad(AA))
    // Otherwise, this is a real load.  If there is a store between the load and
    // end of block, or if the load is volatile, we can't move it.
    return !SawStore && !hasVolatileMemoryRef();

  return true;
}

/// isSafeToReMat - Return true if it's safe to rematerialize the specified
/// instruction which defined the specified register instead of copying it.
bool MachineInstr::isSafeToReMat(const TargetInstrInfo *TII,
                                 AliasAnalysis *AA,
                                 unsigned DstReg) const {
  bool SawStore = false;
  if (!TII->isTriviallyReMaterializable(this, AA) ||
      !isSafeToMove(TII, AA, SawStore))
    return false;
  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = getOperand(i);
    if (!MO.isReg())
      continue;
    // FIXME: For now, do not remat any instruction with register operands.
    // Later on, we can loosen the restriction is the register operands have
    // not been modified between the def and use. Note, this is different from
    // MachineSink because the code is no longer in two-address form (at least
    // partially).
    if (MO.isUse())
      return false;
    else if (!MO.isDead() && MO.getReg() != DstReg)
      return false;
  }
  return true;
}

/// hasVolatileMemoryRef - Return true if this instruction may have a
/// volatile memory reference, or if the information describing the
/// memory reference is not available. Return false if it is known to
/// have no volatile memory references.
bool MachineInstr::hasVolatileMemoryRef() const {
  // An instruction known never to access memory won't have a volatile access.
  if (!TID->mayStore() &&
      !TID->mayLoad() &&
      !TID->isCall() &&
      !TID->hasUnmodeledSideEffects())
    return false;

  // Otherwise, if the instruction has no memory reference information,
  // conservatively assume it wasn't preserved.
  if (memoperands_empty())
    return true;
  
  // Check the memory reference information for volatile references.
  for (mmo_iterator I = memoperands_begin(), E = memoperands_end(); I != E; ++I)
    if ((*I)->isVolatile())
      return true;

  return false;
}

/// isInvariantLoad - Return true if this instruction is loading from a
/// location whose value is invariant across the function.  For example,
/// loading a value from the constant pool or from the argument area
/// of a function if it does not change.  This should only return true of
/// *all* loads the instruction does are invariant (if it does multiple loads).
bool MachineInstr::isInvariantLoad(AliasAnalysis *AA) const {
  // If the instruction doesn't load at all, it isn't an invariant load.
  if (!TID->mayLoad())
    return false;

  // If the instruction has lost its memoperands, conservatively assume that
  // it may not be an invariant load.
  if (memoperands_empty())
    return false;

  const MachineFrameInfo *MFI = getParent()->getParent()->getFrameInfo();

  for (mmo_iterator I = memoperands_begin(),
       E = memoperands_end(); I != E; ++I) {
    if ((*I)->isVolatile()) return false;
    if ((*I)->isStore()) return false;

    if (const Value *V = (*I)->getValue()) {
      // A load from a constant PseudoSourceValue is invariant.
      if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V))
        if (PSV->isConstant(MFI))
          continue;
      // If we have an AliasAnalysis, ask it whether the memory is constant.
      if (AA && AA->pointsToConstantMemory(V))
        continue;
    }

    // Otherwise assume conservatively.
    return false;
  }

  // Everything checks out.
  return true;
}

/// isConstantValuePHI - If the specified instruction is a PHI that always
/// merges together the same virtual register, return the register, otherwise
/// return 0.
unsigned MachineInstr::isConstantValuePHI() const {
  if (!isPHI())
    return 0;
  assert(getNumOperands() >= 3 &&
         "It's illegal to have a PHI without source operands");

  unsigned Reg = getOperand(1).getReg();
  for (unsigned i = 3, e = getNumOperands(); i < e; i += 2)
    if (getOperand(i).getReg() != Reg)
      return 0;
  return Reg;
}

void MachineInstr::dump() const {
  dbgs() << "  " << *this;
}

void MachineInstr::print(raw_ostream &OS, const TargetMachine *TM) const {
  // We can be a bit tidier if we know the TargetMachine and/or MachineFunction.
  const MachineFunction *MF = 0;
  if (const MachineBasicBlock *MBB = getParent()) {
    MF = MBB->getParent();
    if (!TM && MF)
      TM = &MF->getTarget();
  }

  // Print explicitly defined operands on the left of an assignment syntax.
  unsigned StartOp = 0, e = getNumOperands();
  for (; StartOp < e && getOperand(StartOp).isReg() &&
         getOperand(StartOp).isDef() &&
         !getOperand(StartOp).isImplicit();
       ++StartOp) {
    if (StartOp != 0) OS << ", ";
    getOperand(StartOp).print(OS, TM);
  }

  if (StartOp != 0)
    OS << " = ";

  // Print the opcode name.
  OS << getDesc().getName();

  // Print the rest of the operands.
  bool OmittedAnyCallClobbers = false;
  bool FirstOp = true;
  for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = getOperand(i);

    // Omit call-clobbered registers which aren't used anywhere. This makes
    // call instructions much less noisy on targets where calls clobber lots
    // of registers. Don't rely on MO.isDead() because we may be called before
    // LiveVariables is run, or we may be looking at a non-allocatable reg.
    if (MF && getDesc().isCall() &&
        MO.isReg() && MO.isImplicit() && MO.isDef()) {
      unsigned Reg = MO.getReg();
      if (Reg != 0 && TargetRegisterInfo::isPhysicalRegister(Reg)) {
        const MachineRegisterInfo &MRI = MF->getRegInfo();
        if (MRI.use_empty(Reg) && !MRI.isLiveOut(Reg)) {
          bool HasAliasLive = false;
          for (const unsigned *Alias = TM->getRegisterInfo()->getAliasSet(Reg);
               unsigned AliasReg = *Alias; ++Alias)
            if (!MRI.use_empty(AliasReg) || MRI.isLiveOut(AliasReg)) {
              HasAliasLive = true;
              break;
            }
          if (!HasAliasLive) {
            OmittedAnyCallClobbers = true;
            continue;
          }
        }
      }
    }

    if (FirstOp) FirstOp = false; else OS << ",";
    OS << " ";
    if (i < getDesc().NumOperands) {
      const TargetOperandInfo &TOI = getDesc().OpInfo[i];
      if (TOI.isPredicate())
        OS << "pred:";
      if (TOI.isOptionalDef())
        OS << "opt:";
    }
    MO.print(OS, TM);
  }

  // Briefly indicate whether any call clobbers were omitted.
  if (OmittedAnyCallClobbers) {
    if (!FirstOp) OS << ",";
    OS << " ...";
  }

  bool HaveSemi = false;
  if (!memoperands_empty()) {
    if (!HaveSemi) OS << ";"; HaveSemi = true;

    OS << " mem:";
    for (mmo_iterator i = memoperands_begin(), e = memoperands_end();
         i != e; ++i) {
      OS << **i;
      if (next(i) != e)
        OS << " ";
    }
  }

  if (!debugLoc.isUnknown() && MF) {
    if (!HaveSemi) OS << ";";

    // TODO: print InlinedAtLoc information

    DILocation DLT = MF->getDILocation(debugLoc);
    DIScope Scope = DLT.getScope();
    OS << " dbg:";
    // Omit the directory, since it's usually long and uninteresting.
    if (Scope.Verify())
      OS << Scope.getFilename();
    else
      OS << "<unknown>";
    OS << ':' << DLT.getLineNumber();
    if (DLT.getColumnNumber() != 0)
      OS << ':' << DLT.getColumnNumber();
  }

  OS << "\n";
}

bool MachineInstr::addRegisterKilled(unsigned IncomingReg,
                                     const TargetRegisterInfo *RegInfo,
                                     bool AddIfNotFound) {
  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
  bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
  bool Found = false;
  SmallVector<unsigned,4> DeadOps;
  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
    MachineOperand &MO = getOperand(i);
    if (!MO.isReg() || !MO.isUse() || MO.isUndef())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;

    if (Reg == IncomingReg) {
      if (!Found) {
        if (MO.isKill())
          // The register is already marked kill.
          return true;
        if (isPhysReg && isRegTiedToDefOperand(i))
          // Two-address uses of physregs must not be marked kill.
          return true;
        MO.setIsKill();
        Found = true;
      }
    } else if (hasAliases && MO.isKill() &&
               TargetRegisterInfo::isPhysicalRegister(Reg)) {
      // A super-register kill already exists.
      if (RegInfo->isSuperRegister(IncomingReg, Reg))
        return true;
      if (RegInfo->isSubRegister(IncomingReg, Reg))
        DeadOps.push_back(i);
    }
  }

  // Trim unneeded kill operands.
  while (!DeadOps.empty()) {
    unsigned OpIdx = DeadOps.back();
    if (getOperand(OpIdx).isImplicit())
      RemoveOperand(OpIdx);
    else
      getOperand(OpIdx).setIsKill(false);
    DeadOps.pop_back();
  }

  // If not found, this means an alias of one of the operands is killed. Add a
  // new implicit operand if required.
  if (!Found && AddIfNotFound) {
    addOperand(MachineOperand::CreateReg(IncomingReg,
                                         false /*IsDef*/,
                                         true  /*IsImp*/,
                                         true  /*IsKill*/));
    return true;
  }
  return Found;
}

bool MachineInstr::addRegisterDead(unsigned IncomingReg,
                                   const TargetRegisterInfo *RegInfo,
                                   bool AddIfNotFound) {
  bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(IncomingReg);
  bool hasAliases = isPhysReg && RegInfo->getAliasSet(IncomingReg);
  bool Found = false;
  SmallVector<unsigned,4> DeadOps;
  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
    MachineOperand &MO = getOperand(i);
    if (!MO.isReg() || !MO.isDef())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;

    if (Reg == IncomingReg) {
      if (!Found) {
        if (MO.isDead())
          // The register is already marked dead.
          return true;
        MO.setIsDead();
        Found = true;
      }
    } else if (hasAliases && MO.isDead() &&
               TargetRegisterInfo::isPhysicalRegister(Reg)) {
      // There exists a super-register that's marked dead.
      if (RegInfo->isSuperRegister(IncomingReg, Reg))
        return true;
      if (RegInfo->getSubRegisters(IncomingReg) &&
          RegInfo->getSuperRegisters(Reg) &&
          RegInfo->isSubRegister(IncomingReg, Reg))
        DeadOps.push_back(i);
    }
  }

  // Trim unneeded dead operands.
  while (!DeadOps.empty()) {
    unsigned OpIdx = DeadOps.back();
    if (getOperand(OpIdx).isImplicit())
      RemoveOperand(OpIdx);
    else
      getOperand(OpIdx).setIsDead(false);
    DeadOps.pop_back();
  }

  // If not found, this means an alias of one of the operands is dead. Add a
  // new implicit operand if required.
  if (Found || !AddIfNotFound)
    return Found;
    
  addOperand(MachineOperand::CreateReg(IncomingReg,
                                       true  /*IsDef*/,
                                       true  /*IsImp*/,
                                       false /*IsKill*/,
                                       true  /*IsDead*/));
  return true;
}

void MachineInstr::addRegisterDefined(unsigned IncomingReg,
                                      const TargetRegisterInfo *RegInfo) {
  MachineOperand *MO = findRegisterDefOperand(IncomingReg, false, RegInfo);
  if (!MO || MO->getSubReg())
    addOperand(MachineOperand::CreateReg(IncomingReg,
                                         true  /*IsDef*/,
                                         true  /*IsImp*/));
}

unsigned
MachineInstrExpressionTrait::getHashValue(const MachineInstr* const &MI) {
  unsigned Hash = MI->getOpcode() * 37;
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
    uint64_t Key = (uint64_t)MO.getType() << 32;
    switch (MO.getType()) {
    default: break;
    case MachineOperand::MO_Register:
      if (MO.isDef() && MO.getReg() &&
          TargetRegisterInfo::isVirtualRegister(MO.getReg()))
        continue;  // Skip virtual register defs.
      Key |= MO.getReg();
      break;
    case MachineOperand::MO_Immediate:
      Key |= MO.getImm();
      break;
    case MachineOperand::MO_FrameIndex:
    case MachineOperand::MO_ConstantPoolIndex:
    case MachineOperand::MO_JumpTableIndex:
      Key |= MO.getIndex();
      break;
    case MachineOperand::MO_MachineBasicBlock:
      Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
      break;
    case MachineOperand::MO_GlobalAddress:
      Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
      break;
    case MachineOperand::MO_BlockAddress:
      Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
      break;
    case MachineOperand::MO_MCSymbol:
      Key |= DenseMapInfo<void*>::getHashValue(MO.getMCSymbol());
      break;
    }
    Key += ~(Key << 32);
    Key ^= (Key >> 22);
    Key += ~(Key << 13);
    Key ^= (Key >> 8);
    Key += (Key << 3);
    Key ^= (Key >> 15);
    Key += ~(Key << 27);
    Key ^= (Key >> 31);
    Hash = (unsigned)Key + Hash * 37;
  }
  return Hash;
}