llvm.org GIT mirror llvm / release_25 lib / CodeGen / MachineInstr.cpp
release_25

Tree @release_25 (Download .tar.gz)

MachineInstr.cpp @release_25raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
//===-- lib/CodeGen/MachineInstr.cpp --------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Methods common to all machine instructions.
//
//===----------------------------------------------------------------------===//

#include "llvm/Constants.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/Value.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetInstrDesc.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/LeakDetector.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Streams.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/FoldingSet.h"
#include <ostream>
using namespace llvm;

//===----------------------------------------------------------------------===//
// MachineOperand Implementation
//===----------------------------------------------------------------------===//

/// AddRegOperandToRegInfo - Add this register operand to the specified
/// MachineRegisterInfo.  If it is null, then the next/prev fields should be
/// explicitly nulled out.
void MachineOperand::AddRegOperandToRegInfo(MachineRegisterInfo *RegInfo) {
  assert(isReg() && "Can only add reg operand to use lists");
  
  // If the reginfo pointer is null, just explicitly null out or next/prev
  // pointers, to ensure they are not garbage.
  if (RegInfo == 0) {
    Contents.Reg.Prev = 0;
    Contents.Reg.Next = 0;
    return;
  }
  
  // Otherwise, add this operand to the head of the registers use/def list.
  MachineOperand **Head = &RegInfo->getRegUseDefListHead(getReg());
  
  // For SSA values, we prefer to keep the definition at the start of the list.
  // we do this by skipping over the definition if it is at the head of the
  // list.
  if (*Head && (*Head)->isDef())
    Head = &(*Head)->Contents.Reg.Next;
  
  Contents.Reg.Next = *Head;
  if (Contents.Reg.Next) {
    assert(getReg() == Contents.Reg.Next->getReg() &&
           "Different regs on the same list!");
    Contents.Reg.Next->Contents.Reg.Prev = &Contents.Reg.Next;
  }
  
  Contents.Reg.Prev = Head;
  *Head = this;
}

void MachineOperand::setReg(unsigned Reg) {
  if (getReg() == Reg) return; // No change.
  
  // Otherwise, we have to change the register.  If this operand is embedded
  // into a machine function, we need to update the old and new register's
  // use/def lists.
  if (MachineInstr *MI = getParent())
    if (MachineBasicBlock *MBB = MI->getParent())
      if (MachineFunction *MF = MBB->getParent()) {
        RemoveRegOperandFromRegInfo();
        Contents.Reg.RegNo = Reg;
        AddRegOperandToRegInfo(&MF->getRegInfo());
        return;
      }
        
  // Otherwise, just change the register, no problem.  :)
  Contents.Reg.RegNo = Reg;
}

/// ChangeToImmediate - Replace this operand with a new immediate operand of
/// the specified value.  If an operand is known to be an immediate already,
/// the setImm method should be used.
void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
  // If this operand is currently a register operand, and if this is in a
  // function, deregister the operand from the register's use/def list.
  if (isReg() && getParent() && getParent()->getParent() &&
      getParent()->getParent()->getParent())
    RemoveRegOperandFromRegInfo();
  
  OpKind = MO_Immediate;
  Contents.ImmVal = ImmVal;
}

/// ChangeToRegister - Replace this operand with a new register operand of
/// the specified value.  If an operand is known to be an register already,
/// the setReg method should be used.
void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
                                      bool isKill, bool isDead) {
  // If this operand is already a register operand, use setReg to update the 
  // register's use/def lists.
  if (isReg()) {
    assert(!isEarlyClobber());
    setReg(Reg);
  } else {
    // Otherwise, change this to a register and set the reg#.
    OpKind = MO_Register;
    Contents.Reg.RegNo = Reg;

    // If this operand is embedded in a function, add the operand to the
    // register's use/def list.
    if (MachineInstr *MI = getParent())
      if (MachineBasicBlock *MBB = MI->getParent())
        if (MachineFunction *MF = MBB->getParent())
          AddRegOperandToRegInfo(&MF->getRegInfo());
  }

  IsDef = isDef;
  IsImp = isImp;
  IsKill = isKill;
  IsDead = isDead;
  IsEarlyClobber = false;
  SubReg = 0;
}

/// isIdenticalTo - Return true if this operand is identical to the specified
/// operand.
bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
  if (getType() != Other.getType()) return false;
  
  switch (getType()) {
  default: assert(0 && "Unrecognized operand type");
  case MachineOperand::MO_Register:
    return getReg() == Other.getReg() && isDef() == Other.isDef() &&
           getSubReg() == Other.getSubReg();
  case MachineOperand::MO_Immediate:
    return getImm() == Other.getImm();
  case MachineOperand::MO_FPImmediate:
    return getFPImm() == Other.getFPImm();
  case MachineOperand::MO_MachineBasicBlock:
    return getMBB() == Other.getMBB();
  case MachineOperand::MO_FrameIndex:
    return getIndex() == Other.getIndex();
  case MachineOperand::MO_ConstantPoolIndex:
    return getIndex() == Other.getIndex() && getOffset() == Other.getOffset();
  case MachineOperand::MO_JumpTableIndex:
    return getIndex() == Other.getIndex();
  case MachineOperand::MO_GlobalAddress:
    return getGlobal() == Other.getGlobal() && getOffset() == Other.getOffset();
  case MachineOperand::MO_ExternalSymbol:
    return !strcmp(getSymbolName(), Other.getSymbolName()) &&
           getOffset() == Other.getOffset();
  }
}

/// print - Print the specified machine operand.
///
void MachineOperand::print(std::ostream &OS, const TargetMachine *TM) const {
  raw_os_ostream RawOS(OS);
  print(RawOS, TM);
}

void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
  switch (getType()) {
  case MachineOperand::MO_Register:
    if (getReg() == 0 || TargetRegisterInfo::isVirtualRegister(getReg())) {
      OS << "%reg" << getReg();
    } else {
      // If the instruction is embedded into a basic block, we can find the
      // target info for the instruction.
      if (TM == 0)
        if (const MachineInstr *MI = getParent())
          if (const MachineBasicBlock *MBB = MI->getParent())
            if (const MachineFunction *MF = MBB->getParent())
              TM = &MF->getTarget();
      
      if (TM)
        OS << "%" << TM->getRegisterInfo()->get(getReg()).Name;
      else
        OS << "%mreg" << getReg();
    }

    if (getSubReg() != 0) {
      OS << ":" << getSubReg();
    }

    if (isDef() || isKill() || isDead() || isImplicit() || isEarlyClobber()) {
      OS << "<";
      bool NeedComma = false;
      if (isImplicit()) {
        if (NeedComma) OS << ",";
        OS << (isDef() ? "imp-def" : "imp-use");
        NeedComma = true;
      } else if (isDef()) {
        if (NeedComma) OS << ",";
        if (isEarlyClobber())
          OS << "earlyclobber,";
        OS << "def";
        NeedComma = true;
      }
      if (isKill() || isDead()) {
        if (NeedComma) OS << ",";
        if (isKill())  OS << "kill";
        if (isDead())  OS << "dead";
      }
      OS << ">";
    }
    break;
  case MachineOperand::MO_Immediate:
    OS << getImm();
    break;
  case MachineOperand::MO_FPImmediate:
    if (getFPImm()->getType() == Type::FloatTy) {
      OS << getFPImm()->getValueAPF().convertToFloat();
    } else {
      OS << getFPImm()->getValueAPF().convertToDouble();
    }
    break;
  case MachineOperand::MO_MachineBasicBlock:
    OS << "mbb<"
       << ((Value*)getMBB()->getBasicBlock())->getName()
       << "," << (void*)getMBB() << ">";
    break;
  case MachineOperand::MO_FrameIndex:
    OS << "<fi#" << getIndex() << ">";
    break;
  case MachineOperand::MO_ConstantPoolIndex:
    OS << "<cp#" << getIndex();
    if (getOffset()) OS << "+" << getOffset();
    OS << ">";
    break;
  case MachineOperand::MO_JumpTableIndex:
    OS << "<jt#" << getIndex() << ">";
    break;
  case MachineOperand::MO_GlobalAddress:
    OS << "<ga:" << ((Value*)getGlobal())->getName();
    if (getOffset()) OS << "+" << getOffset();
    OS << ">";
    break;
  case MachineOperand::MO_ExternalSymbol:
    OS << "<es:" << getSymbolName();
    if (getOffset()) OS << "+" << getOffset();
    OS << ">";
    break;
  default:
    assert(0 && "Unrecognized operand type");
  }
}

//===----------------------------------------------------------------------===//
// MachineMemOperand Implementation
//===----------------------------------------------------------------------===//

MachineMemOperand::MachineMemOperand(const Value *v, unsigned int f,
                                     int64_t o, uint64_t s, unsigned int a)
  : Offset(o), Size(s), V(v),
    Flags((f & 7) | ((Log2_32(a) + 1) << 3)) {
  assert(isPowerOf2_32(a) && "Alignment is not a power of 2!");
  assert((isLoad() || isStore()) && "Not a load/store!");
}

/// Profile - Gather unique data for the object.
///
void MachineMemOperand::Profile(FoldingSetNodeID &ID) const {
  ID.AddInteger(Offset);
  ID.AddInteger(Size);
  ID.AddPointer(V);
  ID.AddInteger(Flags);
}

//===----------------------------------------------------------------------===//
// MachineInstr Implementation
//===----------------------------------------------------------------------===//

/// MachineInstr ctor - This constructor creates a dummy MachineInstr with
/// TID NULL and no operands.
MachineInstr::MachineInstr()
  : TID(0), NumImplicitOps(0), Parent(0), debugLoc(DebugLoc::getUnknownLoc()) {
  // Make sure that we get added to a machine basicblock
  LeakDetector::addGarbageObject(this);
}

void MachineInstr::addImplicitDefUseOperands() {
  if (TID->ImplicitDefs)
    for (const unsigned *ImpDefs = TID->ImplicitDefs; *ImpDefs; ++ImpDefs)
      addOperand(MachineOperand::CreateReg(*ImpDefs, true, true));
  if (TID->ImplicitUses)
    for (const unsigned *ImpUses = TID->ImplicitUses; *ImpUses; ++ImpUses)
      addOperand(MachineOperand::CreateReg(*ImpUses, false, true));
}

/// MachineInstr ctor - This constructor create a MachineInstr and add the
/// implicit operands. It reserves space for number of operands specified by
/// TargetInstrDesc or the numOperands if it is not zero. (for
/// instructions with variable number of operands).
MachineInstr::MachineInstr(const TargetInstrDesc &tid, bool NoImp)
  : TID(&tid), NumImplicitOps(0), Parent(0), 
    debugLoc(DebugLoc::getUnknownLoc()) {
  if (!NoImp && TID->getImplicitDefs())
    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
      NumImplicitOps++;
  if (!NoImp && TID->getImplicitUses())
    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
      NumImplicitOps++;
  Operands.reserve(NumImplicitOps + TID->getNumOperands());
  if (!NoImp)
    addImplicitDefUseOperands();
  // Make sure that we get added to a machine basicblock
  LeakDetector::addGarbageObject(this);
}

/// MachineInstr ctor - As above, but with a DebugLoc.
MachineInstr::MachineInstr(const TargetInstrDesc &tid, const DebugLoc dl,
                           bool NoImp)
  : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
  if (!NoImp && TID->getImplicitDefs())
    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
      NumImplicitOps++;
  if (!NoImp && TID->getImplicitUses())
    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
      NumImplicitOps++;
  Operands.reserve(NumImplicitOps + TID->getNumOperands());
  if (!NoImp)
    addImplicitDefUseOperands();
  // Make sure that we get added to a machine basicblock
  LeakDetector::addGarbageObject(this);
}

/// MachineInstr ctor - Work exactly the same as the ctor two above, except
/// that the MachineInstr is created and added to the end of the specified 
/// basic block.
///
MachineInstr::MachineInstr(MachineBasicBlock *MBB, const TargetInstrDesc &tid)
  : TID(&tid), NumImplicitOps(0), Parent(0), 
    debugLoc(DebugLoc::getUnknownLoc()) {
  assert(MBB && "Cannot use inserting ctor with null basic block!");
  if (TID->ImplicitDefs)
    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
      NumImplicitOps++;
  if (TID->ImplicitUses)
    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
      NumImplicitOps++;
  Operands.reserve(NumImplicitOps + TID->getNumOperands());
  addImplicitDefUseOperands();
  // Make sure that we get added to a machine basicblock
  LeakDetector::addGarbageObject(this);
  MBB->push_back(this);  // Add instruction to end of basic block!
}

/// MachineInstr ctor - As above, but with a DebugLoc.
///
MachineInstr::MachineInstr(MachineBasicBlock *MBB, const DebugLoc dl,
                           const TargetInstrDesc &tid)
  : TID(&tid), NumImplicitOps(0), Parent(0), debugLoc(dl) {
  assert(MBB && "Cannot use inserting ctor with null basic block!");
  if (TID->ImplicitDefs)
    for (const unsigned *ImpDefs = TID->getImplicitDefs(); *ImpDefs; ++ImpDefs)
      NumImplicitOps++;
  if (TID->ImplicitUses)
    for (const unsigned *ImpUses = TID->getImplicitUses(); *ImpUses; ++ImpUses)
      NumImplicitOps++;
  Operands.reserve(NumImplicitOps + TID->getNumOperands());
  addImplicitDefUseOperands();
  // Make sure that we get added to a machine basicblock
  LeakDetector::addGarbageObject(this);
  MBB->push_back(this);  // Add instruction to end of basic block!
}

/// MachineInstr ctor - Copies MachineInstr arg exactly
///
MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
  : TID(&MI.getDesc()), NumImplicitOps(0), Parent(0), 
        debugLoc(MI.getDebugLoc()) {
  Operands.reserve(MI.getNumOperands());

  // Add operands
  for (unsigned i = 0; i != MI.getNumOperands(); ++i)
    addOperand(MI.getOperand(i));
  NumImplicitOps = MI.NumImplicitOps;

  // Add memory operands.
  for (std::list<MachineMemOperand>::const_iterator i = MI.memoperands_begin(),
       j = MI.memoperands_end(); i != j; ++i)
    addMemOperand(MF, *i);

  // Set parent to null.
  Parent = 0;

  LeakDetector::addGarbageObject(this);
}

MachineInstr::~MachineInstr() {
  LeakDetector::removeGarbageObject(this);
  assert(MemOperands.empty() &&
         "MachineInstr being deleted with live memoperands!");
#ifndef NDEBUG
  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
    assert(Operands[i].ParentMI == this && "ParentMI mismatch!");
    assert((!Operands[i].isReg() || !Operands[i].isOnRegUseList()) &&
           "Reg operand def/use list corrupted");
  }
#endif
}

/// getRegInfo - If this instruction is embedded into a MachineFunction,
/// return the MachineRegisterInfo object for the current function, otherwise
/// return null.
MachineRegisterInfo *MachineInstr::getRegInfo() {
  if (MachineBasicBlock *MBB = getParent())
    return &MBB->getParent()->getRegInfo();
  return 0;
}

/// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
/// this instruction from their respective use lists.  This requires that the
/// operands already be on their use lists.
void MachineInstr::RemoveRegOperandsFromUseLists() {
  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
    if (Operands[i].isReg())
      Operands[i].RemoveRegOperandFromRegInfo();
  }
}

/// AddRegOperandsToUseLists - Add all of the register operands in
/// this instruction from their respective use lists.  This requires that the
/// operands not be on their use lists yet.
void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo) {
  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
    if (Operands[i].isReg())
      Operands[i].AddRegOperandToRegInfo(&RegInfo);
  }
}


/// addOperand - Add the specified operand to the instruction.  If it is an
/// implicit operand, it is added to the end of the operand list.  If it is
/// an explicit operand it is added at the end of the explicit operand list
/// (before the first implicit operand). 
void MachineInstr::addOperand(const MachineOperand &Op) {
  bool isImpReg = Op.isReg() && Op.isImplicit();
  assert((isImpReg || !OperandsComplete()) &&
         "Trying to add an operand to a machine instr that is already done!");

  MachineRegisterInfo *RegInfo = getRegInfo();

  // If we are adding the operand to the end of the list, our job is simpler.
  // This is true most of the time, so this is a reasonable optimization.
  if (isImpReg || NumImplicitOps == 0) {
    // We can only do this optimization if we know that the operand list won't
    // reallocate.
    if (Operands.empty() || Operands.size()+1 <= Operands.capacity()) {
      Operands.push_back(Op);
    
      // Set the parent of the operand.
      Operands.back().ParentMI = this;
  
      // If the operand is a register, update the operand's use list.
      if (Op.isReg())
        Operands.back().AddRegOperandToRegInfo(RegInfo);
      return;
    }
  }
  
  // Otherwise, we have to insert a real operand before any implicit ones.
  unsigned OpNo = Operands.size()-NumImplicitOps;

  // If this instruction isn't embedded into a function, then we don't need to
  // update any operand lists.
  if (RegInfo == 0) {
    // Simple insertion, no reginfo update needed for other register operands.
    Operands.insert(Operands.begin()+OpNo, Op);
    Operands[OpNo].ParentMI = this;

    // Do explicitly set the reginfo for this operand though, to ensure the
    // next/prev fields are properly nulled out.
    if (Operands[OpNo].isReg())
      Operands[OpNo].AddRegOperandToRegInfo(0);

  } else if (Operands.size()+1 <= Operands.capacity()) {
    // Otherwise, we have to remove register operands from their register use
    // list, add the operand, then add the register operands back to their use
    // list.  This also must handle the case when the operand list reallocates
    // to somewhere else.
  
    // If insertion of this operand won't cause reallocation of the operand
    // list, just remove the implicit operands, add the operand, then re-add all
    // the rest of the operands.
    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
      assert(Operands[i].isReg() && "Should only be an implicit reg!");
      Operands[i].RemoveRegOperandFromRegInfo();
    }
    
    // Add the operand.  If it is a register, add it to the reg list.
    Operands.insert(Operands.begin()+OpNo, Op);
    Operands[OpNo].ParentMI = this;

    if (Operands[OpNo].isReg())
      Operands[OpNo].AddRegOperandToRegInfo(RegInfo);
    
    // Re-add all the implicit ops.
    for (unsigned i = OpNo+1, e = Operands.size(); i != e; ++i) {
      assert(Operands[i].isReg() && "Should only be an implicit reg!");
      Operands[i].AddRegOperandToRegInfo(RegInfo);
    }
  } else {
    // Otherwise, we will be reallocating the operand list.  Remove all reg
    // operands from their list, then readd them after the operand list is
    // reallocated.
    RemoveRegOperandsFromUseLists();
    
    Operands.insert(Operands.begin()+OpNo, Op);
    Operands[OpNo].ParentMI = this;
  
    // Re-add all the operands.
    AddRegOperandsToUseLists(*RegInfo);
  }
}

/// RemoveOperand - Erase an operand  from an instruction, leaving it with one
/// fewer operand than it started with.
///
void MachineInstr::RemoveOperand(unsigned OpNo) {
  assert(OpNo < Operands.size() && "Invalid operand number");
  
  // Special case removing the last one.
  if (OpNo == Operands.size()-1) {
    // If needed, remove from the reg def/use list.
    if (Operands.back().isReg() && Operands.back().isOnRegUseList())
      Operands.back().RemoveRegOperandFromRegInfo();
    
    Operands.pop_back();
    return;
  }

  // Otherwise, we are removing an interior operand.  If we have reginfo to
  // update, remove all operands that will be shifted down from their reg lists,
  // move everything down, then re-add them.
  MachineRegisterInfo *RegInfo = getRegInfo();
  if (RegInfo) {
    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
      if (Operands[i].isReg())
        Operands[i].RemoveRegOperandFromRegInfo();
    }
  }
  
  Operands.erase(Operands.begin()+OpNo);

  if (RegInfo) {
    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
      if (Operands[i].isReg())
        Operands[i].AddRegOperandToRegInfo(RegInfo);
    }
  }
}

/// addMemOperand - Add a MachineMemOperand to the machine instruction,
/// referencing arbitrary storage.
void MachineInstr::addMemOperand(MachineFunction &MF,
                                 const MachineMemOperand &MO) {
  MemOperands.push_back(MO);
}

/// clearMemOperands - Erase all of this MachineInstr's MachineMemOperands.
void MachineInstr::clearMemOperands(MachineFunction &MF) {
  MemOperands.clear();
}


/// removeFromParent - This method unlinks 'this' from the containing basic
/// block, and returns it, but does not delete it.
MachineInstr *MachineInstr::removeFromParent() {
  assert(getParent() && "Not embedded in a basic block!");
  getParent()->remove(this);
  return this;
}


/// eraseFromParent - This method unlinks 'this' from the containing basic
/// block, and deletes it.
void MachineInstr::eraseFromParent() {
  assert(getParent() && "Not embedded in a basic block!");
  getParent()->erase(this);
}


/// OperandComplete - Return true if it's illegal to add a new operand
///
bool MachineInstr::OperandsComplete() const {
  unsigned short NumOperands = TID->getNumOperands();
  if (!TID->isVariadic() && getNumOperands()-NumImplicitOps >= NumOperands)
    return true;  // Broken: we have all the operands of this instruction!
  return false;
}

/// getNumExplicitOperands - Returns the number of non-implicit operands.
///
unsigned MachineInstr::getNumExplicitOperands() const {
  unsigned NumOperands = TID->getNumOperands();
  if (!TID->isVariadic())
    return NumOperands;

  for (unsigned e = getNumOperands(); NumOperands != e; ++NumOperands) {
    const MachineOperand &MO = getOperand(NumOperands);
    if (!MO.isReg() || !MO.isImplicit())
      NumOperands++;
  }
  return NumOperands;
}


/// isLabel - Returns true if the MachineInstr represents a label.
///
bool MachineInstr::isLabel() const {
  return getOpcode() == TargetInstrInfo::DBG_LABEL ||
         getOpcode() == TargetInstrInfo::EH_LABEL ||
         getOpcode() == TargetInstrInfo::GC_LABEL;
}

/// isDebugLabel - Returns true if the MachineInstr represents a debug label.
///
bool MachineInstr::isDebugLabel() const {
  return getOpcode() == TargetInstrInfo::DBG_LABEL;
}

/// findRegisterUseOperandIdx() - Returns the MachineOperand that is a use of
/// the specific register or -1 if it is not found. It further tightening
/// the search criteria to a use that kills the register if isKill is true.
int MachineInstr::findRegisterUseOperandIdx(unsigned Reg, bool isKill,
                                          const TargetRegisterInfo *TRI) const {
  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = getOperand(i);
    if (!MO.isReg() || !MO.isUse())
      continue;
    unsigned MOReg = MO.getReg();
    if (!MOReg)
      continue;
    if (MOReg == Reg ||
        (TRI &&
         TargetRegisterInfo::isPhysicalRegister(MOReg) &&
         TargetRegisterInfo::isPhysicalRegister(Reg) &&
         TRI->isSubRegister(MOReg, Reg)))
      if (!isKill || MO.isKill())
        return i;
  }
  return -1;
}
  
/// findRegisterDefOperandIdx() - Returns the operand index that is a def of
/// the specified register or -1 if it is not found. If isDead is true, defs
/// that are not dead are skipped. If TargetRegisterInfo is non-null, then it
/// also checks if there is a def of a super-register.
int MachineInstr::findRegisterDefOperandIdx(unsigned Reg, bool isDead,
                                          const TargetRegisterInfo *TRI) const {
  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = getOperand(i);
    if (!MO.isReg() || !MO.isDef())
      continue;
    unsigned MOReg = MO.getReg();
    if (MOReg == Reg ||
        (TRI &&
         TargetRegisterInfo::isPhysicalRegister(MOReg) &&
         TargetRegisterInfo::isPhysicalRegister(Reg) &&
         TRI->isSubRegister(MOReg, Reg)))
      if (!isDead || MO.isDead())
        return i;
  }
  return -1;
}

/// findFirstPredOperandIdx() - Find the index of the first operand in the
/// operand list that is used to represent the predicate. It returns -1 if
/// none is found.
int MachineInstr::findFirstPredOperandIdx() const {
  const TargetInstrDesc &TID = getDesc();
  if (TID.isPredicable()) {
    for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
      if (TID.OpInfo[i].isPredicate())
        return i;
  }

  return -1;
}
  
/// isRegReDefinedByTwoAddr - Given the index of a register def operand,
/// check if the register def is a re-definition due to two addr elimination.
bool MachineInstr::isRegReDefinedByTwoAddr(unsigned DefIdx) const{
  assert(getOperand(DefIdx).isDef() && "DefIdx is not a def!");
  const TargetInstrDesc &TID = getDesc();
  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = getOperand(i);
    if (MO.isReg() && MO.isUse() &&
        TID.getOperandConstraint(i, TOI::TIED_TO) == (int)DefIdx)
      return true;
  }
  return false;
}

/// copyKillDeadInfo - Copies kill / dead operand properties from MI.
///
void MachineInstr::copyKillDeadInfo(const MachineInstr *MI) {
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
    if (!MO.isReg() || (!MO.isKill() && !MO.isDead()))
      continue;
    for (unsigned j = 0, ee = getNumOperands(); j != ee; ++j) {
      MachineOperand &MOp = getOperand(j);
      if (!MOp.isIdenticalTo(MO))
        continue;
      if (MO.isKill())
        MOp.setIsKill();
      else
        MOp.setIsDead();
      break;
    }
  }
}

/// copyPredicates - Copies predicate operand(s) from MI.
void MachineInstr::copyPredicates(const MachineInstr *MI) {
  const TargetInstrDesc &TID = MI->getDesc();
  if (!TID.isPredicable())
    return;
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    if (TID.OpInfo[i].isPredicate()) {
      // Predicated operands must be last operands.
      addOperand(MI->getOperand(i));
    }
  }
}

/// isSafeToMove - Return true if it is safe to move this instruction. If
/// SawStore is set to true, it means that there is a store (or call) between
/// the instruction's location and its intended destination.
bool MachineInstr::isSafeToMove(const TargetInstrInfo *TII,
                                bool &SawStore) const {
  // Ignore stuff that we obviously can't move.
  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() && !TII->isInvariantLoad(this))
    // Otherwise, this is a real load.  If there is a store between the load and
    // end of block, or if the laod 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,
                                 unsigned DstReg) const {
  bool SawStore = false;
  if (!getDesc().isRematerializable() ||
      !TII->isTriviallyReMaterializable(this) ||
      !isSafeToMove(TII, 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 (std::list<MachineMemOperand>::const_iterator I = memoperands_begin(),
       E = memoperands_end(); I != E; ++I)
    if (I->isVolatile())
      return true;

  return false;
}

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

void MachineInstr::print(std::ostream &OS, const TargetMachine *TM) const {
  raw_os_ostream RawOS(OS);
  print(RawOS, TM);
}

void MachineInstr::print(raw_ostream &OS, const TargetMachine *TM) const {
  // Specialize printing if op#0 is definition
  unsigned StartOp = 0;
  if (getNumOperands() && getOperand(0).isReg() && getOperand(0).isDef()) {
    getOperand(0).print(OS, TM);
    OS << " = ";
    ++StartOp;   // Don't print this operand again!
  }

  OS << getDesc().getName();

  for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
    if (i != StartOp)
      OS << ",";
    OS << " ";
    getOperand(i).print(OS, TM);
  }

  if (!memoperands_empty()) {
    OS << ", Mem:";
    for (std::list<MachineMemOperand>::const_iterator i = memoperands_begin(),
         e = memoperands_end(); i != e; ++i) {
      const MachineMemOperand &MRO = *i;
      const Value *V = MRO.getValue();

      assert((MRO.isLoad() || MRO.isStore()) &&
             "SV has to be a load, store or both.");
      
      if (MRO.isVolatile())
        OS << "Volatile ";

      if (MRO.isLoad())
        OS << "LD";
      if (MRO.isStore())
        OS << "ST";
        
      OS << "(" << MRO.getSize() << "," << MRO.getAlignment() << ") [";
      
      if (!V)
        OS << "<unknown>";
      else if (!V->getName().empty())
        OS << V->getName();
      else if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) {
        PSV->print(OS);
      } else
        OS << V;

      OS << " + " << MRO.getOffset() << "]";
    }
  }

  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())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;

    if (Reg == IncomingReg) {
      if (!Found) {
        if (MO.isKill())
          // The register is already 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) {
    addOperand(MachineOperand::CreateReg(IncomingReg,
                                         true  /*IsDef*/,
                                         true  /*IsImp*/,
                                         false /*IsKill*/,
                                         true  /*IsDead*/));
    return true;
  }
  return Found;
}