X-Git-Url: http://plrg.eecs.uci.edu/git/?p=repair.git;a=blobdiff_plain;f=Repair%2FRepairCompiler%2FMCC%2FIR%2FDotExpr.java;h=54133026fdc63f38a933a044e3796cea27d1f3db;hp=c7ed42fbd157e3ffbffa025b8f313b3ffec47a7a;hb=87862c69c1cb47c83a858f0b6e52d9c0bc25913f;hpb=0092f02d48abd3603fa7c5115e8f5a63ada45f68

diff --git a/Repair/RepairCompiler/MCC/IR/DotExpr.java b/Repair/RepairCompiler/MCC/IR/DotExpr.java
index c7ed42f..5413302 100755
--- a/Repair/RepairCompiler/MCC/IR/DotExpr.java
+++ b/Repair/RepairCompiler/MCC/IR/DotExpr.java
@@ -1,18 +1,86 @@
 package MCC.IR;
 
 import java.util.*;
+import MCC.Compiler;
 
 public class DotExpr extends Expr {
-    
+
     Expr left;
     String field;
     Expr index;
 
+    static boolean DOMEMCHECKS=false;
+    static boolean DOTYPECHECKS=false;
+    static boolean DONULL=false;
+
+
+    public DotExpr(Expr left, String field, Expr index) {
+        this.left = left;
+        this.field = field;
+        this.index = index;
+    }
+
+    public boolean isInvariant(Set vars) {
+	if (!left.isInvariant(vars))
+	    return false;
+	if (intindex!=null)
+	    return intindex.isInvariant(vars);
+	else
+	    return true;
+    }
+
+    public Set findInvariants(Set vars) {
+	if (isInvariant(vars)) {
+	    Set s=new HashSet();
+	    s.add(this);
+	    return s;
+	} else {
+	    Set ls=left.findInvariants(vars);
+	    if (intindex!=null) {
+		ls.addAll(intindex.findInvariants(vars));
+		Expr indexbound=((ArrayDescriptor)this.fd).getIndexBound();
+		ls.addAll(indexbound.findInvariants(vars));
+		if ((!(intindex instanceof IntegerLiteralExpr))||
+		    ((IntegerLiteralExpr) intindex).getValue() != 0) {
+		    FieldDescriptor fd=this.fd;
+		    if (fd instanceof ArrayDescriptor)
+			fd=((ArrayDescriptor)fd).getField();
+		    Expr basesize = fd.getBaseSizeExpr();
+		    ls.addAll(basesize.findInvariants(vars));
+		}
+	    }
+	    return ls;
+	}
+    }
+
+
+    public boolean isSafe() {
+	if (!left.isSafe())
+	    return false;
+
+	FieldDescriptor tmpfd=fd;
+
+	if (tmpfd.getPtr()) // Pointers cound be invalid
+	    return false;
+
+	if (tmpfd instanceof ArrayDescriptor) {
+            Expr arrayindex=((ArrayDescriptor)tmpfd).getIndexBound();
+            if (index instanceof IntegerLiteralExpr&&arrayindex instanceof IntegerLiteralExpr) {
+                int indexvalue=((IntegerLiteralExpr)index).getValue();
+                int arrayindexvalue=((IntegerLiteralExpr)arrayindex).getValue();
+                if (indexvalue>=0&&indexvalue<arrayindexvalue)
+                    return true;
+            }
+	    return false; // Otherwise, arrays could be out of bounds
+        }
+        return true;
+    }
+
     public Set freeVars() {
 	Set lset=left.freeVars();
 	Set iset=null;
-	if (index!=null)
-	    iset=index.freeVars();
+	if (intindex!=null)
+	    iset=intindex.freeVars();
 	if (lset==null)
 	    return iset;
 	if (iset!=null)
@@ -42,7 +110,25 @@ public class DotExpr extends Expr {
 	    name+="["+index.name()+"]";
 	return name;
     }
-    
+
+    public void findmatch(Descriptor d, Set s) {
+	if (d==fd)
+	    s.add(this);
+	left.findmatch(d,s);
+	if (intindex!=null)
+	    intindex.findmatch(d,s);
+    }
+
+    public Set useDescriptor(Descriptor d) {
+	HashSet newset=new HashSet();
+	if (d==fd)
+	    newset.add(this);
+	newset.addAll(left.useDescriptor(d));
+	if (intindex!=null)
+	    newset.addAll(intindex.useDescriptor(d));
+	return newset;
+    }
+
     public boolean usesDescriptor(Descriptor d) {
 	if (d==fd)
 	    return true;
@@ -65,19 +151,14 @@ public class DotExpr extends Expr {
 	return true;
     }
 
-    
-    public DotExpr(Expr left, String field, Expr index) {
-        this.left = left;
-        this.field = field;
-        this.index = index;
-    }
 
     public Set getRequiredDescriptors() {
         Set v = left.getRequiredDescriptors();
-        
-        if (index != null) {
-            v.addAll(index.getRequiredDescriptors());
+
+        if (intindex != null) {
+            v.addAll(intindex.getRequiredDescriptors());
         }
+        v.add(fd);
         return v;
     }
 
@@ -96,162 +177,174 @@ public class DotExpr extends Expr {
     public void generate(CodeWriter writer, VarDescriptor dest) {
         VarDescriptor leftd = VarDescriptor.makeNew("left");
 
-        writer.output("// " +  leftd.getSafeSymbol() + " <-- ");
+	if (writer.getInvariantValue()!=null&&
+	    writer.getInvariantValue().isInvariant(this)) {
+	    writer.addDeclaration(getType().getGenerateType().getSafeSymbol().toString(), dest.getSafeSymbol());
+	    writer.outputline(dest.getSafeSymbol()+"="+writer.getInvariantValue().getValue(this).getSafeSymbol()+";");
+	    writer.outputline("maybe="+writer.getInvariantValue().getMaybe(this).getSafeSymbol()+";");
+	    return;
+	}
+
+        writer.output("/* " +  leftd.getSafeSymbol() + " <-- ");
         left.prettyPrint(writer);
-        writer.outputline("");
+        writer.outputline("*/");
 
         left.generate(writer, leftd);
 
-        writer.output("// " +  leftd.getSafeSymbol() + " = ");
+        writer.output("/* " +  leftd.getSafeSymbol() + " = ");
         left.prettyPrint(writer);
-        writer.outputline("");
-      
-        StructureTypeDescriptor struct = (StructureTypeDescriptor) left.getType();        
-        Expr intindex = index;
+        writer.outputline("*/");
+
+        StructureTypeDescriptor struct = (StructureTypeDescriptor) left.getType();
         Expr offsetbits;
 
-        // #ATTN#: getOffsetExpr needs to be called with the fielddescriptor obect that is in teh vector list
-        // this means that if the field is an arraydescriptor you have to call getOffsetExpr with the array 
+        // #ATTN#: getOffsetExpr needs to be called with the fielddescriptor object that is in the vector list
+        // this means that if the field is an arraydescriptor you have to call getOffsetExpr with the array
         // descriptor not the underlying field descriptor
 
         /* we calculate the offset in bits */
+
         offsetbits = struct.getOffsetExpr(fd);
 
-        if (fd instanceof ArrayDescriptor) {
-            fd = ((ArrayDescriptor) fd).getField();
-        } 
-        
+	FieldDescriptor fd=this.fd;
+	if (fd instanceof ArrayDescriptor)
+	    fd=((ArrayDescriptor)fd).getField();
+	boolean doboundscheck=true;
+	boolean performedboundscheck=false;
+
+	writer.addDeclaration(getType().getGenerateType().toString(),dest.getSafeSymbol());
+	writer.outputline(dest.getSafeSymbol()+"=0;");
+
         if (intindex != null) {
             if (intindex instanceof IntegerLiteralExpr && ((IntegerLiteralExpr) intindex).getValue() == 0) {
-                /* short circuit for constant 0 */                
+                /* short circuit for constant 0 */
             } else {
                 Expr basesize = fd.getBaseSizeExpr();
-                offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
-            }
-        }
-        
-        final SymbolTable st = writer.getSymbolTable();
-        TypeDescriptor td = offsetbits.typecheck(new SemanticAnalyzer() {
-                public IRErrorReporter getErrorReporter() { throw new IRException("badness"); }
-                public SymbolTable getSymbolTable() { return st; }
-            });
-
-        if (td == null) {
-            throw new IRException();
-        } else if (td != ReservedTypeDescriptor.INT) {
-            throw new IRException();
-        }
-               
-        // #TBD#: ptr's to bits and byte's and stuff are a little iffy... 
-        // right now, a bit* is the same as a int* = short* = byte* (that is there 
-        // is no post-derefernce mask)
-        
-        // #ATTN#: do we handle int* correctly? what is the correct behavior? we automatically 
-        // dereference pointers, but for structures that means that if we have a nested structure
-        // we return an integer address to that nested structure. if we have a pointer to a 
-        // structure else where we want that base address ... yeah so we *(int *) it... ok we are
-        // correct
-
-        boolean dotypecheck = false;
-
-        if (offsetbits instanceof IntegerLiteralExpr) {
-            int offsetinbits = ((IntegerLiteralExpr) offsetbits).getValue();
-            int offset = offsetinbits >> 3; /* offset in bytes */
-
-            if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
-                int shift = offsetinbits - (offset << 3);            
-                int mask = bitmask(((IntegerLiteralExpr)fd.getType().getSizeExpr()).getValue());
-                               
-                /* type var = ((*(int *) (base + offset)) >> shift) & mask */
-                writer.outputline(getType().getGenerateType() + " " + dest.getSafeSymbol() + 
-                                  " = ((*(int *)" + 
-                                  "(" + leftd.getSafeSymbol() + " + " + offset + ")) " + 
-                                  " >> " + shift + ") & 0x" + Integer.toHexString(mask) + ";");  
-            } else { /* a structure address or a ptr! */
-                String ptr = fd.getPtr() ? "*(int *)" : "";
-                /* type var = [*(int *)] (base + offset) */
-
-                // #ATTN: was 'getType.getGeneratedType()' instead of 'int' but all pointers are represented
-                // by integers
-                writer.outputline("int " + dest.getSafeSymbol() + 
-                                  " = " + ptr + "(" + leftd.getSafeSymbol() + " + " + offset + ");");  
-
-                dotypecheck = true;
-            }
-        } else { /* offset in bits is an expression that must be generated */                        
-            VarDescriptor ob = VarDescriptor.makeNew("offsetinbits");
-            writer.output("// " + ob.getSafeSymbol() + " <-- ");
-            offsetbits.prettyPrint(writer);
-            writer.outputline("");
-            offsetbits.generate(writer, ob);
-            writer.output("// " + ob.getSafeSymbol() + " = ");
-            offsetbits.prettyPrint(writer);
-            writer.outputline("");
-
-            /* derive offset in bytes */
-            VarDescriptor offset = VarDescriptor.makeNew("offset");
-            writer.outputline("int " + offset.getSafeSymbol() + " = " + ob.getSafeSymbol() + " >> 3;");
-            
-            if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
-                VarDescriptor shift = VarDescriptor.makeNew("shift");
-                writer.outputline("int " + shift.getSafeSymbol() + " = " + ob.getSafeSymbol() + 
-                                  " - (" + offset.getSafeSymbol() + " << 3);");
-                int mask = bitmask(((IntegerLiteralExpr)fd.getType().getSizeExpr()).getValue());
-                
-                /* type var = ((*(int *) (base + offset)) >> shift) & mask */
-                writer.outputline(getType().getGenerateType() + " " + dest.getSafeSymbol() + 
-                                  " = ((*(int *)" + 
-                                  "(" + leftd.getSafeSymbol() + " + " + offset.getSafeSymbol() + ")) " + 
-                                  " >> " + shift.getSafeSymbol() + ") & 0x" + Integer.toHexString(mask) + ";");  
-            } else { /* a structure address or a ptr */
-                String ptr = fd.getPtr() ? "*(int *)" : "";
-                /* type var = [*(int *)] (base + offset) */
-
-                // #ATTN: was 'getType.getGeneratedType()' instead of 'int' but all pointers are represented
-                // by integers
-                writer.outputline("int " + dest.getSafeSymbol() + 
-                                  " = " + ptr + "(" + leftd.getSafeSymbol() + " + " + offset.getSafeSymbol() + ");");  
-                dotypecheck = true;
+		if (doboundscheck) {
+		    VarDescriptor indexvd=VarDescriptor.makeNew("index");
+		    indexvd.setType(ReservedTypeDescriptor.INT);
+		    writer.getSymbolTable().add(indexvd);
+
+		    writer.output("/* " + indexvd.getSafeSymbol() + " <-- ");
+
+		    intindex.prettyPrint(writer);
+		    writer.outputline("*/");
+		    intindex.generate(writer, indexvd);
+		    writer.output("/* " + indexvd.getSafeSymbol() + " = ");
+		    intindex.prettyPrint(writer);
+		    writer.outputline("*/");
+		    Expr indexbound=((ArrayDescriptor)this.fd).getIndexBound();
+		    VarDescriptor indexboundvd=VarDescriptor.makeNew("indexbound");
+
+		    indexbound.generate(writer,indexboundvd);
+
+		    writer.outputline("if ("+indexvd.getSafeSymbol()+">=0 &&"+indexvd.getSafeSymbol()+"<"+indexboundvd.getSafeSymbol()+")");
+		    writer.startblock();
+		    VarExpr indexve=new VarExpr(indexvd);
+		    offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, indexve));
+
+		    performedboundscheck=true;
+		} else
+		    offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
             }
         }
 
+	final SymbolTable st = writer.getSymbolTable();
+        TypeDescriptor td2 = offsetbits.typecheck(new SemanticAnalyzer() {
+		public IRErrorReporter getErrorReporter() { throw new IRException("badness"); }
+		public SymbolTable getSymbolTable() { return st; }
+	    });
 
-        if (dotypecheck) { /* typemap checks! */
-            // dest is 'low'
-            // high is 'low' + sizeof(fd.getDataStructure) <<< can be cached!!
-
-            // #ATTN#: we need to get the size of the fieldtype (if its a label the type of the label, not the 
-            // underlying field's type
-
-            Expr sizeofexpr = fieldtype.getSizeExpr();
-            VarDescriptor sizeof = VarDescriptor.makeNew("sizeof");
-            sizeofexpr.generate(writer, sizeof);
+        if (td2 == null) {
+	    throw new IRException();
+        } else if (td2 != ReservedTypeDescriptor.INT) {
+	    throw new IRException();
+	}
 
-            String low = dest.getSafeSymbol();
-            String high = VarDescriptor.makeNew("high").getSafeSymbol();
-            writer.outputline("int " + high + " = " + low + " + " + sizeof.getSafeSymbol() + ";");            
-            writer.outputline("assertvalidmemory(" + low + ", " + high + ");");            
+        boolean dotypecheck = false;
 
-            // we need to null value check and conditionalize the rest of the rule... we'll use a hack
-            // here where we store the number of indents in this class... and then provide a static 
-            // method to unwind...
-            //writer.outputline("// assertvalidmemory ");
-            //DotExpr.memoryindents++;
-            //writer.outputline("if (" + dest.getSafeSymbol() + " != NULL)");
-            //writer.startblock();           
+	VarDescriptor ob = VarDescriptor.makeNew("offsetinbits");
+	writer.output("/* " + ob.getSafeSymbol() + " <-- ");
+	offsetbits.prettyPrint(writer);
+	writer.outputline("*/");
+	offsetbits.generate(writer, ob);
+	writer.output("/* " + ob.getSafeSymbol() + " = ");
+	offsetbits.prettyPrint(writer);
+	writer.outputline("*/");
+
+	/* derive offset in bytes */
+	VarDescriptor offset = VarDescriptor.makeNew("offset");
+	writer.addDeclaration("int", offset.getSafeSymbol());
+	writer.outputline(offset.getSafeSymbol() + " = " + ob.getSafeSymbol() + " >> 3;");
+
+	if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
+	    VarDescriptor shift = VarDescriptor.makeNew("shift");
+	    writer.addDeclaration("int", shift.getSafeSymbol());
+	    writer.outputline(shift.getSafeSymbol() + " = " + ob.getSafeSymbol() +
+			      " - (" + offset.getSafeSymbol() + " << 3);");
+	    int mask = bitmask(((IntegerLiteralExpr)fd.getType().getSizeExpr()).getValue());
+
+	    /* type var = ((*(int *) (base + offset)) >> shift) & mask */
+	    writer.outputline("if ("+leftd.getSafeSymbol()+")");
+	    writer.outputline(dest.getSafeSymbol() + " = ((*(int *)" +
+			      "(" + leftd.getSafeSymbol() + " + " + offset.getSafeSymbol() + ")) " +
+			      " >> " + shift.getSafeSymbol() + ") & 0x" + Integer.toHexString(mask) + ";");
+	    writer.outputline("else maybe=1;");
+	} else { /* a structure address or a ptr */
+	    String ptr = fd.getPtr() ? "*(int *)" : "";
+	    /* type var = [*(int *)] (base + offset) */
+	    writer.outputline("if ("+leftd.getSafeSymbol()+")");
+	    writer.startblock();
+	    writer.outputline(dest.getSafeSymbol() +
+			      " = " + ptr + "(" + leftd.getSafeSymbol() + " + " + offset.getSafeSymbol() + ");");
+	    if (fd.getPtr()) {
+		writer.outputline("if ("+dest.getSafeSymbol()+")");
+		writer.startblock();
+		VarDescriptor typevar=VarDescriptor.makeNew("typechecks");
+		if (DOMEMCHECKS&&(!DOTYPECHECKS)) {
+		    writer.addDeclaration("bool", typevar.getSafeSymbol());
+		    writer.outputline(typevar.getSafeSymbol()+"=assertvalidmemory(" + dest.getSafeSymbol() + ", " + this.td.getId() + ");");
+		    dotypecheck = true;
+		} else if (DOTYPECHECKS) {
+		    writer.addDeclaration("bool", typevar.getSafeSymbol());
+		    writer.outputline(typevar.getSafeSymbol()+"=assertvalidtype(" + dest.getSafeSymbol() + ", " + this.td.getId() + ");");
+		}
+
+		if (DOTYPECHECKS||DOMEMCHECKS) {
+		    writer.outputline("if (!"+typevar.getSafeSymbol()+")");
+		    writer.startblock();
+		    writer.outputline(dest.getSafeSymbol()+"=0;");
+		    if (DONULL)
+			writer.outputline(ptr + "(" + leftd.getSafeSymbol() + " + " + offset.getSafeSymbol() + ")=0;");
+		    writer.endblock();
+		}
+
+		writer.endblock();
+	    }
+	    writer.endblock();
+	    writer.outputline("else maybe=1;");
         }
-
+	if (performedboundscheck) {
+	    writer.endblock();
+	    writer.outputline(" else ");
+	    writer.startblock();
+	    writer.outputline(dest.getSafeSymbol()+"=0;");
+	    writer.outputline("maybe=1;");
+	    if (!Compiler.REPAIR)
+		writer.outputline("printf(\"Array Index Out of Bounds\");");
+	    writer.endblock();
+	}
     }
 
     private int bitmask(int bits) {
         int mask = 0;
-        
+
         for (int i = 0; i < bits; i++) {
             mask <<= 1;
             mask += 1;
         }
 
-        return mask;            
+        return mask;
     }
 
     public void prettyPrint(PrettyPrinter pp) {
@@ -264,13 +357,31 @@ public class DotExpr extends Expr {
         }
     }
 
+    public boolean isValue(TypeDescriptor td) {
+	FieldDescriptor tmpfd=fd;
+	if (tmpfd instanceof ArrayDescriptor)
+	    tmpfd=((ArrayDescriptor)tmpfd).getField();
+	return (tmpfd.getPtr()||(tmpfd.getType() instanceof ReservedTypeDescriptor));
+    }
+
+    public boolean isPtr() {
+	FieldDescriptor tmpfd=fd;
+	if (tmpfd instanceof ArrayDescriptor)
+	    tmpfd=((ArrayDescriptor)tmpfd).getField();
+	return tmpfd.getPtr();
+    }
+
+    boolean typechecked=false;
     public TypeDescriptor typecheck(SemanticAnalyzer sa) {
+	if (typechecked)
+	    return this.td;
+	else typechecked=true;
         TypeDescriptor lefttype = left.typecheck(sa);
         TypeDescriptor indextype = index == null ? null : index.typecheck(sa);
-	
+
 	{
 	    /* finished typechecking...so we can fill the fields in */
-	    StructureTypeDescriptor struct = (StructureTypeDescriptor) left.getType();        
+	    StructureTypeDescriptor struct = (StructureTypeDescriptor) left.getType();
 	    FieldDescriptor fd = struct.getField(field);
 	    LabelDescriptor ld = struct.getLabel(field);
 	    if (ld != null) { /* label */
@@ -281,10 +392,15 @@ public class DotExpr extends Expr {
 		assert intindex == null;
 		intindex = ld.getIndex();
 	    } else {
+                if (fd==null) {
+                    throw new Error("Null fd for: "+field);
+                }
 		fieldtype = fd.getType();
 		intindex=index;
 	    }
 	    this.fd=fd;
+	    if (fieldtype instanceof MissingTypeDescriptor)
+		throw new Error(fieldtype.getSymbol()+" type undefined!");
 	}
 
         if ((lefttype == null) || (index != null && indextype == null)) {
@@ -298,7 +414,7 @@ public class DotExpr extends Expr {
             }
         }
 
-        if (lefttype instanceof StructureTypeDescriptor) {            
+        if (lefttype instanceof StructureTypeDescriptor) {
             StructureTypeDescriptor struct = (StructureTypeDescriptor) lefttype;
             FieldDescriptor fd = struct.getField(field);
             LabelDescriptor ld = struct.getLabel(field);
@@ -308,21 +424,21 @@ public class DotExpr extends Expr {
 
                 if (indextype == null && fd instanceof ArrayDescriptor) {
                     sa.getErrorReporter().report(null, "Must specify an index what accessing array field '" + struct.getSymbol() + "." + fd.getSymbol() + "'");
-                    return null;                
+                    return null;
                 } else if (indextype != null && !(fd instanceof ArrayDescriptor)) {
                     sa.getErrorReporter().report(null, "Cannot specify an index when accessing non-array field '" + struct.getSymbol() + "." + fd.getSymbol() + "'");
                     return null;
                 }
-                
+
                 this.td = fd.getType();
             } else if (ld != null) { /* label */
                 assert fd == null;
 
-                if (index != null) { 
+                if (index != null) {
                     sa.getErrorReporter().report(null, "A label cannot be accessed as an array");
                     return null;
                 }
-                
+
                 this.td = ld.getType();
             } else {
                 sa.getErrorReporter().report(null, "No such field or label '" + field + "' in structure '" + struct.getSymbol() + "'");
@@ -341,9 +457,5 @@ public class DotExpr extends Expr {
             sa.getErrorReporter().report(null, "Left hand side of . expression must be a structure type, not '" + lefttype.getSymbol() + "'");
             return null;
         }
-        
-        
     }
-
 }
-