SSA renaming fix & invalid opcode fix
The old SSA renaming mechanism was able to take some shortcuts because
of the limited CFG shapes it encountered. Shortcut replaced and previous
workaround code removed.
Also fixes a regression introduced by the stack bounds checking change
which sometimes resulted in an (opcode < 0x200) assert failure, and
removes an optimization flag and associated code that no longer applicable.
Change-Id: I617e9e5347dfd3a7e8f44a9772647bf4530631d6
diff --git a/src/compiler/CompilerIR.h b/src/compiler/CompilerIR.h
index 0c83a94..e2418b8 100644
--- a/src/compiler/CompilerIR.h
+++ b/src/compiler/CompilerIR.h
@@ -215,6 +215,7 @@
/* The following are new data structures to support SSA representations */
/* Map original Dalvik reg i to the SSA[15..0]/Sub[31..16] pair */
int* dalvikToSSAMap; // length == method->registersSize
+ int* SSALastDefs; // length == method->registersSize
ArenaBitVector* isConstantV; // length == numSSAReg
int* constantValues; // length == numSSAReg
diff --git a/src/compiler/Dataflow.cc b/src/compiler/Dataflow.cc
index 06f942f..3369e9e 100644
--- a/src/compiler/Dataflow.cc
+++ b/src/compiler/Dataflow.cc
@@ -1931,10 +1931,9 @@
static void handleSSADef(CompilationUnit* cUnit, int* defs, int dalvikReg,
int regIndex)
{
- int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
int ssaReg = cUnit->numSSARegs++;
/* Bump up the subscript */
- int dalvikSub = DECODE_SUB(encodedValue) + 1;
+ int dalvikSub = ++cUnit->SSALastDefs[dalvikReg];
int newD2SMapping = ENCODE_REG_SUB(ssaReg, dalvikSub);
cUnit->dalvikToSSAMap[dalvikReg] = newD2SMapping;
@@ -1982,6 +1981,10 @@
if (bb->dataFlowInfo == NULL) return false;
+ if (cUnit->printMeVerbose) {
+ LOG(INFO) << "oatDoSSAConversion processing block " << bb->id;
+ }
+
for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
mir->ssaRep = (struct SSARepresentation *)
oatNew(sizeof(SSARepresentation), true);
@@ -1989,14 +1992,17 @@
int dfAttributes =
oatDataFlowAttributes[mir->dalvikInsn.opcode];
- int flags = dexGetFlagsFromOpcode(mir->dalvikInsn.opcode);
+ // If not a pseudo-op, note non-leaf or can throw
+ if (mir->dalvikInsn.opcode < kNumPackedOpcodes) {
+ int flags = dexGetFlagsFromOpcode(mir->dalvikInsn.opcode);
- if (flags & kInstrCanThrow) {
- cUnit->attrs &= ~METHOD_IS_THROW_FREE;
- }
+ if (flags & kInstrCanThrow) {
+ cUnit->attrs &= ~METHOD_IS_THROW_FREE;
+ }
- if (flags & kInstrInvoke) {
- cUnit->attrs &= ~METHOD_IS_LEAF;
+ if (flags & kInstrInvoke) {
+ cUnit->attrs &= ~METHOD_IS_LEAF;
+ }
}
int numUses = 0;
@@ -2222,8 +2228,13 @@
*/
cUnit->dalvikToSSAMap = (int *)oatNew(sizeof(int) * numDalvikReg,
false);
+ /* Keep track of the higest def for each dalvik reg */
+ cUnit->SSALastDefs = (int *)oatNew(sizeof(int) * numDalvikReg,
+ false);
+
for (i = 0; i < numDalvikReg; i++) {
cUnit->dalvikToSSAMap[i] = i;
+ cUnit->SSALastDefs[i] = 0;
}
/*
diff --git a/src/compiler/Frontend.cc b/src/compiler/Frontend.cc
index 887ae71..c419f1a 100644
--- a/src/compiler/Frontend.cc
+++ b/src/compiler/Frontend.cc
@@ -701,7 +701,6 @@
cUnit.disableOpt = 0 |
(1 << kLoadStoreElimination) |
(1 << kLoadHoisting) |
- (1 << kTrackLiveTemps) |
(1 << kSuppressLoads) |
(1 << kPromoteRegs) |
0;
diff --git a/src/compiler/SSATransformation.cc b/src/compiler/SSATransformation.cc
index 95f6db5..dea1971 100644
--- a/src/compiler/SSATransformation.cc
+++ b/src/compiler/SSATransformation.cc
@@ -548,6 +548,48 @@
return true;
}
+static void doDFSPreOrderSSARename(CompilationUnit* cUnit, BasicBlock* block)
+{
+
+ if (block->visited || block->hidden) return;
+ block->visited = true;
+
+ /* Process this block */
+ oatDoSSAConversion(cUnit, block);
+ int mapSize = sizeof(int) * cUnit->method->NumRegisters();
+
+ /* Save SSA map snapshot */
+ int* savedSSAMap = (int*)oatNew(mapSize, false);
+ memcpy(savedSSAMap, cUnit->dalvikToSSAMap, mapSize);
+
+ if (block->fallThrough) {
+ doDFSPreOrderSSARename(cUnit, block->fallThrough);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize);
+ }
+ if (block->taken) {
+ doDFSPreOrderSSARename(cUnit, block->taken);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize);
+ }
+ if (block->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ oatGrowableListIteratorInit(&block->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock* succBB = successorBlockInfo->block;
+ doDFSPreOrderSSARename(cUnit, succBB);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize);
+ }
+ }
+ cUnit->dalvikToSSAMap = savedSSAMap;
+ return;
+}
+
/* Perform SSA transformation for the whole method */
void oatMethodSSATransformation(CompilationUnit* cUnit)
{
@@ -567,9 +609,10 @@
insertPhiNodes(cUnit);
/* Rename register names by local defs and phi nodes */
- oatDataFlowAnalysisDispatcher(cUnit, oatDoSSAConversion,
- kPreOrderDFSTraversal,
+ oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
+ kAllNodes,
false /* isIterative */);
+ doDFSPreOrderSSARename(cUnit, cUnit->entryBlock);
/*
* Shared temp bit vector used by each block to count the number of defs
diff --git a/src/compiler/codegen/Optimizer.h b/src/compiler/codegen/Optimizer.h
index c485717..b234587 100644
--- a/src/compiler/codegen/Optimizer.h
+++ b/src/compiler/codegen/Optimizer.h
@@ -26,7 +26,6 @@
enum optControlVector {
kLoadStoreElimination = 0,
kLoadHoisting,
- kTrackLiveTemps,
kSuppressLoads,
kPromoteRegs,
};
diff --git a/src/compiler/codegen/RallocUtil.cc b/src/compiler/codegen/RallocUtil.cc
index 76cff17..8295b33 100644
--- a/src/compiler/codegen/RallocUtil.cc
+++ b/src/compiler/codegen/RallocUtil.cc
@@ -1004,38 +1004,15 @@
return loc;
}
-/*
- * There's currently a problem in SSA renaming. So long as register promotion
- * is disabled, a bad renaming will have no effect. Work around the problem
- * here to make progress while the fix is being identified.
- */
-#define SSA_WORKAROUND
-
extern RegLocation oatGetDest(CompilationUnit* cUnit, MIR* mir, int num)
{
RegLocation res = cUnit->regLocation[mir->ssaRep->defs[num]];
-#ifdef SSA_WORKAROUND
- if (res.wide) {
- LOG(WARNING) << "Invalid SSA renaming: " << PrettyMethod(cUnit->method);
- cUnit->printMe = true;
- cUnit->dumpCFG = true;
- res.wide = false;
- }
-#endif
assert(!res.wide);
return res;
}
extern RegLocation oatGetSrc(CompilationUnit* cUnit, MIR* mir, int num)
{
RegLocation res = cUnit->regLocation[mir->ssaRep->uses[num]];
-#ifdef SSA_WORKAROUND
- if (res.wide) {
- LOG(WARNING) << "Invalid SSA renaming: " << PrettyMethod(cUnit->method);
- cUnit->printMe = true;
- cUnit->dumpCFG = true;
- res.wide = false;
- }
-#endif
assert(!res.wide);
return res;
}
@@ -1048,14 +1025,6 @@
int low, int high)
{
RegLocation res = cUnit->regLocation[mir->ssaRep->defs[low]];
-#ifdef SSA_WORKAROUND
- if (!res.wide) {
- LOG(WARNING) << "Invalid SSA renaming: " << PrettyMethod(cUnit->method);
- cUnit->printMe = true;
- cUnit->dumpCFG = true;
- res.wide = true;
- }
-#endif
assert(res.wide);
return res;
}
@@ -1064,14 +1033,6 @@
int low, int high)
{
RegLocation res = cUnit->regLocation[mir->ssaRep->uses[low]];
-#ifdef SSA_WORKAROUND
- if (!res.wide) {
- LOG(WARNING) << "Invalid SSA renaming: " << PrettyMethod(cUnit->method);
- cUnit->printMe = true;
- cUnit->dumpCFG = true;
- res.wide = true;
- }
-#endif
assert(res.wide);
return res;
}
diff --git a/src/compiler/codegen/arm/MethodCodegenDriver.cc b/src/compiler/codegen/arm/MethodCodegenDriver.cc
index 8070e8d..10f470d 100644
--- a/src/compiler/codegen/arm/MethodCodegenDriver.cc
+++ b/src/compiler/codegen/arm/MethodCodegenDriver.cc
@@ -1878,9 +1878,7 @@
for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
oatResetRegPool(cUnit);
- if (cUnit->disableOpt & (1 << kTrackLiveTemps)) {
- oatClobberAllRegs(cUnit);
- }
+ oatClobberAllRegs(cUnit);
if (cUnit->disableOpt & (1 << kSuppressLoads)) {
oatResetDefTracking(cUnit);
diff --git a/src/compiler_test.cc b/src/compiler_test.cc
index ee407ef..6784981 100644
--- a/src/compiler_test.cc
+++ b/src/compiler_test.cc
@@ -155,6 +155,11 @@
}
}
+TEST_F(CompilerTest, ByBillion) {
+ CompileDirectMethod(NULL, "java.lang.Object", "<init>", "()V");
+ AssertStaticLongMethod(123, LoadDex("IntMath"), "IntMath", "divideLongByBillion", "(J)J", 123000000000LL);
+}
+
TEST_F(CompilerTest, BasicCodegen) {
AssertStaticIntMethod(55, LoadDex("Fibonacci"), "Fibonacci", "fibonacci", "(I)I", 10);
}
diff --git a/test/IntMath/IntMath.java b/test/IntMath/IntMath.java
index 758e6df..4c445b7 100644
--- a/test/IntMath/IntMath.java
+++ b/test/IntMath/IntMath.java
@@ -25,6 +25,31 @@
foo_ = 123;
}
+ /* Regression test: triggered an SSA renaming bug. */
+ static long divideLongByBillion(long a) {
+ long quot;
+ long rem;
+
+ if (a >= 0) {
+ long bLong = 1000000000L;
+ quot = (a / bLong);
+ rem = (a % bLong);
+ } else {
+ /*
+ * Make the dividend positive shifting it right by 1 bit then get
+ * the quotient an remainder and correct them properly
+ */
+ long aPos = a >>> 1;
+ long bPos = 1000000000L >>> 1;
+ quot = aPos / bPos;
+ rem = aPos % bPos;
+ // double the remainder and add 1 if 'a' is odd
+ rem = (rem << 1) + (a & 1);
+ }
+ return ((rem << 32) | (quot & 0xFFFFFFFFL));
+ }
+
+
static int instanceTest(int x) {
IntMathBase a = new IntMathBase();
IntMath b = new IntMath();
@@ -734,7 +759,16 @@
}
public static void main(String[] args) {
- int res = unopTest(38);
+ int res;
+ long lres;
+
+ lres = divideLongByBillion(123000000000L);
+ if (lres == 123) {
+ System.out.println("divideLongByBillion PASSED");
+ } else {
+ System.out.println("divideLongByBillion FAILED: " + lres);
+ }
+ res = unopTest(38);
if (res == 37) {
System.out.println("unopTest PASSED");
} else {
@@ -782,7 +816,7 @@
} else {
System.out.println("longOperTest FAILED: " + res);
}
- long lres = longShiftTest(0xd5aa96deff00aa01L, 16);
+ lres = longShiftTest(0xd5aa96deff00aa01L, 16);
if (lres == 0x96deff00aa010000L) {
System.out.println("longShiftTest PASSED");
} else {