Really fix PR1734. Carefully track which register uses are sub-register uses by

traversing inverse register coalescing map.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43118 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 128 insertions, 14 deletions

diff --git a/include/llvm/CodeGen/SimpleRegisterCoalescing.h b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
index 93d3e1d..b62c26c 100644
--- a/include/llvm/CodeGen/SimpleRegisterCoalescing.h
+++ b/include/llvm/CodeGen/SimpleRegisterCoalescing.h
@@ -37,19 +37,24 @@ namespace llvm {
     LiveIntervals *li_;
     LiveVariables *lv_;
     
-    typedef IndexedMap<unsigned> Reg2RegMap;
-    Reg2RegMap r2rMap_;
-
     BitVector allocatableRegs_;
     DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_;
 
+    /// r2rMap_ - Map from register to its representative register.
+    ///
+    IndexedMap<unsigned> r2rMap_;
+
+    /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all
+    /// the registers it represent.
+    IndexedMap<std::vector<unsigned> > r2rRevMap_;
+
     /// JoinedLIs - Keep track which register intervals have been coalesced
     /// with other intervals.
     BitVector JoinedLIs;
 
-    /// SubRegIdxes - Keep track of sub-register and sub-indexes.
+    /// SubRegIdxes - Keep track of sub-register and indexes.
     ///
-    std::vector<std::pair<unsigned, unsigned> > SubRegIdxes;
+    SmallVector<std::pair<unsigned, unsigned>, 32> SubRegIdxes;
 
   public:
     static char ID; // Pass identifcation, replacement for typeid
@@ -132,10 +137,15 @@ namespace llvm {
     bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
                               MachineInstr *CopyMI);
 
+    /// AddSubRegIdxPairs - Recursively mark all the registers represented by the
+    /// specified register as sub-registers. The recursion level is expected to be
+    /// shallow.
+    void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx);
+
     /// lastRegisterUse - Returns the last use of the specific register between
     /// cycles Start and End. It also returns the use operand by reference. It
     /// returns NULL if there are no uses.
-     MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
+    MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
                                   MachineOperand *&MOU);
 
     /// findDefOperand - Returns the MachineOperand that is a def of the specific
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index ee2cbbb..b2c29fc 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -57,7 +57,6 @@ namespace {
 const PassInfo *llvm::SimpleRegisterCoalescingID = X.getPassInfo();
 
 void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
-   //AU.addPreserved<LiveVariables>();
   AU.addPreserved<LiveIntervals>();
   AU.addPreservedID(PHIEliminationID);
   AU.addPreservedID(TwoAddressInstructionPassID);
@@ -185,6 +184,17 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte
   return true;
 }
 
+/// AddSubRegIdxPairs - Recursively mark all the registers represented by the
+/// specified register as sub-registers. The recursion level is expected to be
+/// shallow.
+void SimpleRegisterCoalescing::AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx) {
+  std::vector<unsigned> &JoinedRegs = r2rRevMap_[Reg];
+  for (unsigned i = 0, e = JoinedRegs.size(); i != e; ++i) {
+    SubRegIdxes.push_back(std::make_pair(JoinedRegs[i], SubIdx));
+    AddSubRegIdxPairs(JoinedRegs[i], SubIdx);
+  }
+}
+
 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 /// if the copy was successfully coalesced away, or if it is never possible
@@ -459,8 +469,9 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
       std::swap(repSrcReg, repDstReg);
       std::swap(ResSrcInt, ResDstInt);
     }
-    SubRegIdxes.push_back(std::make_pair(DstReg,
-                                         CopyMI->getOperand(2).getImm()));
+    unsigned SubIdx = CopyMI->getOperand(2).getImm();
+    SubRegIdxes.push_back(std::make_pair(repSrcReg, SubIdx));
+    AddSubRegIdxPairs(repSrcReg, SubIdx);
   }
 
   DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, mri_);
@@ -470,6 +481,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
   // being merged.
   li_->removeInterval(repSrcReg);
   r2rMap_[repSrcReg] = repDstReg;
+  r2rRevMap_[repDstReg].push_back(repSrcReg);
 
   // Finally, delete the copy instruction.
   li_->RemoveMachineInstrFromMaps(CopyMI);
@@ -1039,7 +1051,7 @@ void SimpleRegisterCoalescing::joinIntervals() {
   }
   
   DOUT << "*** Register mapping ***\n";
-  for (int i = 0, e = r2rMap_.size(); i != e; ++i)
+  for (unsigned i = 0, e = r2rMap_.size(); i != e; ++i)
     if (r2rMap_[i]) {
       DOUT << "  reg " << i << " -> ";
       DEBUG(printRegName(r2rMap_[i]));
@@ -1172,9 +1184,12 @@ void SimpleRegisterCoalescing::printRegName(unsigned reg) const {
 }
 
 void SimpleRegisterCoalescing::releaseMemory() {
-   r2rMap_.clear();
-   JoinedLIs.clear();
-   SubRegIdxes.clear();
+  for (unsigned i = 0, e = r2rMap_.size(); i != e; ++i)
+    r2rRevMap_[i].clear();
+  r2rRevMap_.clear();
+  r2rMap_.clear();
+  JoinedLIs.clear();
+  SubRegIdxes.clear();
 }
 
 static bool isZeroLengthInterval(LiveInterval *li) {
@@ -1204,6 +1219,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
 
   SSARegMap *RegMap = mf_->getSSARegMap();
   r2rMap_.grow(RegMap->getLastVirtReg());
+  r2rRevMap_.grow(RegMap->getLastVirtReg());
 
   // Join (coalesce) intervals if requested.
   if (EnableJoining) {
@@ -1214,7 +1230,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
       DOUT << "\n";
     }
 
-    // Track coalesced sub-registers.
+    // Transfer sub-registers info to SSARegMap now that coalescing information
+    // is complete.
     while (!SubRegIdxes.empty()) {
       std::pair<unsigned, unsigned> RI = SubRegIdxes.back();
       SubRegIdxes.pop_back();
diff --git a/test/CodeGen/X86/2007-10-17-IllegalAsm.ll b/test/CodeGen/X86/2007-10-17-IllegalAsm.ll
new file mode 100644
index 0000000..f3cdfee
--- /dev/null
+++ b/test/CodeGen/X86/2007-10-17-IllegalAsm.ll
@@ -0,0 +1,87 @@
+; RUN: llvm-as < %s | llc -mtriple=x86_64-linux-gnu | grep addb | not grep x
+; RUN: llvm-as < %s | llc -mtriple=x86_64-linux-gnu | grep cmpb | not grep x
+; PR1734
+
+target triple = "x86_64-unknown-linux-gnu"
+	%struct.CUMULATIVE_ARGS = type { i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
+	%struct.eh_status = type opaque
+	%struct.emit_status = type { i32, i32, %struct.rtx_def*, %struct.rtx_def*, %struct.sequence_stack*, i32, %struct.location_t, i32, i8*, %struct.rtx_def** }
+	%struct.expr_status = type { i32, i32, i32, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def* }
+	%struct.function = type { %struct.eh_status*, %struct.expr_status*, %struct.emit_status*, %struct.varasm_status*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.function*, i32, i32, i32, i32, %struct.rtx_def*, %struct.CUMULATIVE_ARGS, %struct.rtx_def*, %struct.rtx_def*, %struct.initial_value_struct*, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def*, %struct.rtx_def*, i8, i32, i64, %struct.tree_node*, %struct.tree_node*, %struct.rtx_def*, %struct.varray_head_tag*, %struct.temp_slot*, i32, %struct.var_refs_queue*, i32, i32, %struct.rtvec_def*, %struct.tree_node*, i32, i32, i32, %struct.machine_function*, i32, i32, i8, i8, %struct.language_function*, %struct.rtx_def*, i32, i32, i32, i32, %struct.location_t, %struct.varray_head_tag*, %struct.tree_node*, %struct.tree_node*, i8, i8, i8 }
+	%struct.initial_value_struct = type opaque
+	%struct.lang_decl = type opaque
+	%struct.language_function = type opaque
+	%struct.location_t = type { i8*, i32 }
+	%struct.machine_function = type { %struct.stack_local_entry*, i8*, %struct.rtx_def*, i32, i32, i32, i32, i32 }
+	%struct.rtunion = type { i8* }
+	%struct.rtvec_def = type { i32, [1 x %struct.rtx_def*] }
+	%struct.rtx_def = type { i16, i8, i8, %struct.u }
+	%struct.sequence_stack = type { %struct.rtx_def*, %struct.rtx_def*, %struct.sequence_stack* }
+	%struct.stack_local_entry = type opaque
+	%struct.temp_slot = type opaque
+	%struct.tree_common = type { %struct.tree_node*, %struct.tree_node*, %union.tree_ann_d*, i8, i8, i8, i8, i8 }
+	%struct.tree_decl = type { %struct.tree_common, %struct.location_t, i32, %struct.tree_node*, i8, i8, i8, i8, i8, i8, i8, i8, i32, %struct.tree_decl_u1, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.tree_node*, %struct.rtx_def*, i32, %struct.tree_decl_u2, %struct.tree_node*, %struct.tree_node*, i64, %struct.lang_decl* }
+	%struct.tree_decl_u1 = type { i64 }
+	%struct.tree_decl_u2 = type { %struct.function* }
+	%struct.tree_node = type { %struct.tree_decl }
+	%struct.u = type { [1 x %struct.rtunion] }
+	%struct.var_refs_queue = type { %struct.rtx_def*, i32, i32, %struct.var_refs_queue* }
+	%struct.varasm_status = type opaque
+	%struct.varray_data = type { [1 x i64] }
+	%struct.varray_head_tag = type { i64, i64, i32, i8*, %struct.varray_data }
+	%union.tree_ann_d = type opaque
+
+define void @layout_type(%struct.tree_node* %type) {
+entry:
+	%tmp32 = load i32* null, align 8		; <i32> [#uses=3]
+	%tmp3435 = trunc i32 %tmp32 to i8		; <i8> [#uses=1]
+	%tmp53 = icmp eq %struct.tree_node* null, null		; <i1> [#uses=1]
+	br i1 %tmp53, label %cond_next57, label %UnifiedReturnBlock
+
+cond_next57:		; preds = %entry
+	%tmp65 = and i32 %tmp32, 255		; <i32> [#uses=1]
+	switch i32 %tmp65, label %UnifiedReturnBlock [
+		 i32 6, label %bb140
+		 i32 7, label %bb140
+		 i32 8, label %bb140
+		 i32 13, label %bb478
+	]
+
+bb140:		; preds = %cond_next57, %cond_next57, %cond_next57
+	%tmp219 = load i32* null, align 8		; <i32> [#uses=1]
+	%tmp221222 = trunc i32 %tmp219 to i8		; <i8> [#uses=1]
+	%tmp223 = icmp eq i8 %tmp221222, 24		; <i1> [#uses=1]
+	br i1 %tmp223, label %cond_true226, label %cond_next340
+
+cond_true226:		; preds = %bb140
+	switch i8 %tmp3435, label %cond_true288 [
+		 i8 6, label %cond_next340
+		 i8 9, label %cond_next340
+		 i8 7, label %cond_next340
+		 i8 8, label %cond_next340
+		 i8 10, label %cond_next340
+	]
+
+cond_true288:		; preds = %cond_true226
+	unreachable
+
+cond_next340:		; preds = %cond_true226, %cond_true226, %cond_true226, %cond_true226, %cond_true226, %bb140
+	ret void
+
+bb478:		; preds = %cond_next57
+	br i1 false, label %cond_next500, label %cond_true497
+
+cond_true497:		; preds = %bb478
+	unreachable
+
+cond_next500:		; preds = %bb478
+	%tmp513 = load i32* null, align 8		; <i32> [#uses=1]
+	%tmp545 = and i32 %tmp513, 8192		; <i32> [#uses=1]
+	%tmp547 = and i32 %tmp32, -8193		; <i32> [#uses=1]
+	%tmp548 = or i32 %tmp547, %tmp545		; <i32> [#uses=1]
+	store i32 %tmp548, i32* null, align 8
+	ret void
+
+UnifiedReturnBlock:		; preds = %cond_next57, %entry
+	ret void
+}