Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(242)

Side by Side Diff: src/arm/lithium-codegen-arm.cc

Issue 190383002: Handle non-power-of-2 divisors in division-like operations (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Rebased Created 6 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/arm/lithium-codegen-arm.h ('k') | src/arm/macro-assembler-arm.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2012 the V8 project authors. All rights reserved. 1 // Copyright 2012 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 1126 matching lines...) Expand 10 before | Expand all | Expand 10 after
1137 } 1137 }
1138 __ b(&done); 1138 __ b(&done);
1139 } 1139 }
1140 1140
1141 __ bind(&dividend_is_not_negative); 1141 __ bind(&dividend_is_not_negative);
1142 __ and_(dividend, dividend, Operand(mask)); 1142 __ and_(dividend, dividend, Operand(mask));
1143 __ bind(&done); 1143 __ bind(&done);
1144 } 1144 }
1145 1145
1146 1146
1147 void LCodeGen::DoModByConstI(LModByConstI* instr) {
1148 Register dividend = ToRegister(instr->dividend());
1149 int32_t divisor = instr->divisor();
1150 Register result = ToRegister(instr->result());
1151 ASSERT(!dividend.is(result));
1152
1153 if (divisor == 0) {
1154 DeoptimizeIf(al, instr->environment());
1155 return;
1156 }
1157
1158 __ FlooringDiv(result, dividend, Abs(divisor));
1159 __ mov(ip, Operand(Abs(divisor)));
1160 __ smull(result, ip, result, ip);
1161 __ sub(result, dividend, result, SetCC);
1162
1163 // Check for negative zero.
1164 HMod* hmod = instr->hydrogen();
1165 if (hmod->CheckFlag(HValue::kBailoutOnMinusZero) &&
1166 hmod->left()->CanBeNegative()) {
1167 Label remainder_not_zero;
1168 __ b(ne, &remainder_not_zero);
1169 __ cmp(dividend, Operand::Zero());
1170 DeoptimizeIf(lt, instr->environment());
1171 __ bind(&remainder_not_zero);
1172 }
1173 }
1174
1175
1147 void LCodeGen::DoModI(LModI* instr) { 1176 void LCodeGen::DoModI(LModI* instr) {
1148 HMod* hmod = instr->hydrogen(); 1177 HMod* hmod = instr->hydrogen();
1149 HValue* left = hmod->left(); 1178 HValue* left = hmod->left();
1150 HValue* right = hmod->right(); 1179 HValue* right = hmod->right();
1151 if (CpuFeatures::IsSupported(SUDIV)) { 1180 if (CpuFeatures::IsSupported(SUDIV)) {
1152 CpuFeatureScope scope(masm(), SUDIV); 1181 CpuFeatureScope scope(masm(), SUDIV);
1153 1182
1154 Register left_reg = ToRegister(instr->left()); 1183 Register left_reg = ToRegister(instr->left());
1155 Register right_reg = ToRegister(instr->right()); 1184 Register right_reg = ToRegister(instr->right());
1156 Register result_reg = ToRegister(instr->result()); 1185 Register result_reg = ToRegister(instr->result());
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after
1251 hmod->CheckFlag(HValue::kBailoutOnMinusZero)) { 1280 hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
1252 __ b(ne, &done); 1281 __ b(ne, &done);
1253 __ cmp(left_reg, Operand::Zero()); 1282 __ cmp(left_reg, Operand::Zero());
1254 DeoptimizeIf(mi, instr->environment()); 1283 DeoptimizeIf(mi, instr->environment());
1255 } 1284 }
1256 __ bind(&done); 1285 __ bind(&done);
1257 } 1286 }
1258 } 1287 }
1259 1288
1260 1289
1261 void LCodeGen::EmitSignedIntegerDivisionByConstant(
1262 Register result,
1263 Register dividend,
1264 int32_t divisor,
1265 Register remainder,
1266 Register scratch,
1267 LEnvironment* environment) {
1268 ASSERT(!AreAliased(dividend, scratch, ip));
1269 ASSERT(LChunkBuilder::HasMagicNumberForDivisor(divisor));
1270
1271 uint32_t divisor_abs = abs(divisor);
1272
1273 int32_t power_of_2_factor =
1274 CompilerIntrinsics::CountTrailingZeros(divisor_abs);
1275
1276 switch (divisor_abs) {
1277 case 0:
1278 DeoptimizeIf(al, environment);
1279 return;
1280
1281 case 1:
1282 if (divisor > 0) {
1283 __ Move(result, dividend);
1284 } else {
1285 __ rsb(result, dividend, Operand::Zero(), SetCC);
1286 DeoptimizeIf(vs, environment);
1287 }
1288 // Compute the remainder.
1289 __ mov(remainder, Operand::Zero());
1290 return;
1291
1292 default:
1293 if (IsPowerOf2(divisor_abs)) {
1294 // Branch and condition free code for integer division by a power
1295 // of two.
1296 int32_t power = WhichPowerOf2(divisor_abs);
1297 if (power > 1) {
1298 __ mov(scratch, Operand(dividend, ASR, power - 1));
1299 }
1300 __ add(scratch, dividend, Operand(scratch, LSR, 32 - power));
1301 __ mov(result, Operand(scratch, ASR, power));
1302 // Negate if necessary.
1303 // We don't need to check for overflow because the case '-1' is
1304 // handled separately.
1305 if (divisor < 0) {
1306 ASSERT(divisor != -1);
1307 __ rsb(result, result, Operand::Zero());
1308 }
1309 // Compute the remainder.
1310 if (divisor > 0) {
1311 __ sub(remainder, dividend, Operand(result, LSL, power));
1312 } else {
1313 __ add(remainder, dividend, Operand(result, LSL, power));
1314 }
1315 return;
1316 } else {
1317 // Use magic numbers for a few specific divisors.
1318 // Details and proofs can be found in:
1319 // - Hacker's Delight, Henry S. Warren, Jr.
1320 // - The PowerPC Compiler Writer’s Guide
1321 // and probably many others.
1322 //
1323 // We handle
1324 // <divisor with magic numbers> * <power of 2>
1325 // but not
1326 // <divisor with magic numbers> * <other divisor with magic numbers>
1327 DivMagicNumbers magic_numbers =
1328 DivMagicNumberFor(divisor_abs >> power_of_2_factor);
1329 // Branch and condition free code for integer division by a power
1330 // of two.
1331 const int32_t M = magic_numbers.M;
1332 const int32_t s = magic_numbers.s + power_of_2_factor;
1333
1334 __ mov(ip, Operand(M));
1335 __ smull(ip, scratch, dividend, ip);
1336 if (M < 0) {
1337 __ add(scratch, scratch, Operand(dividend));
1338 }
1339 if (s > 0) {
1340 __ mov(scratch, Operand(scratch, ASR, s));
1341 }
1342 __ add(result, scratch, Operand(dividend, LSR, 31));
1343 if (divisor < 0) __ rsb(result, result, Operand::Zero());
1344 // Compute the remainder.
1345 __ mov(ip, Operand(divisor));
1346 // This sequence could be replaced with 'mls' when
1347 // it gets implemented.
1348 __ mul(scratch, result, ip);
1349 __ sub(remainder, dividend, scratch);
1350 }
1351 }
1352 }
1353
1354
1355 void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) { 1290 void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) {
1356 Register dividend = ToRegister(instr->dividend()); 1291 Register dividend = ToRegister(instr->dividend());
1357 int32_t divisor = instr->divisor(); 1292 int32_t divisor = instr->divisor();
1358 Register result = ToRegister(instr->result()); 1293 Register result = ToRegister(instr->result());
1359 ASSERT(divisor == kMinInt || (divisor != 0 && IsPowerOf2(Abs(divisor)))); 1294 ASSERT(divisor == kMinInt || (divisor != 0 && IsPowerOf2(Abs(divisor))));
1360 ASSERT(!result.is(dividend)); 1295 ASSERT(!result.is(dividend));
1361 1296
1362 // Check for (0 / -x) that will produce negative zero. 1297 // Check for (0 / -x) that will produce negative zero.
1363 HDiv* hdiv = instr->hydrogen(); 1298 HDiv* hdiv = instr->hydrogen();
1364 if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) && 1299 if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) &&
(...skipping 26 matching lines...) Expand all
1391 __ add(result, dividend, Operand(dividend, LSR, 31)); 1326 __ add(result, dividend, Operand(dividend, LSR, 31));
1392 } else { 1327 } else {
1393 __ mov(result, Operand(dividend, ASR, 31)); 1328 __ mov(result, Operand(dividend, ASR, 31));
1394 __ add(result, dividend, Operand(result, LSR, 32 - shift)); 1329 __ add(result, dividend, Operand(result, LSR, 32 - shift));
1395 } 1330 }
1396 if (shift > 0) __ mov(result, Operand(result, ASR, shift)); 1331 if (shift > 0) __ mov(result, Operand(result, ASR, shift));
1397 if (divisor < 0) __ rsb(result, result, Operand(0)); 1332 if (divisor < 0) __ rsb(result, result, Operand(0));
1398 } 1333 }
1399 1334
1400 1335
1336 void LCodeGen::DoDivByConstI(LDivByConstI* instr) {
1337 Register dividend = ToRegister(instr->dividend());
1338 int32_t divisor = instr->divisor();
1339 Register result = ToRegister(instr->result());
1340 ASSERT(!dividend.is(result));
1341
1342 if (divisor == 0) {
1343 DeoptimizeIf(al, instr->environment());
1344 return;
1345 }
1346
1347 // Check for (0 / -x) that will produce negative zero.
1348 HDiv* hdiv = instr->hydrogen();
1349 if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) &&
1350 hdiv->left()->RangeCanInclude(0) && divisor < 0) {
1351 __ cmp(dividend, Operand::Zero());
1352 DeoptimizeIf(eq, instr->environment());
1353 }
1354
1355 __ FlooringDiv(result, dividend, Abs(divisor));
1356 if (divisor < 0) __ rsb(result, result, Operand::Zero());
1357
1358 if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) {
1359 __ mov(ip, Operand(divisor));
1360 __ smull(scratch0(), ip, result, ip);
1361 __ sub(scratch0(), scratch0(), dividend, SetCC);
1362 DeoptimizeIf(ne, instr->environment());
1363 }
1364 }
1365
1366
1401 void LCodeGen::DoDivI(LDivI* instr) { 1367 void LCodeGen::DoDivI(LDivI* instr) {
1402 const Register left = ToRegister(instr->left()); 1368 const Register left = ToRegister(instr->left());
1403 const Register right = ToRegister(instr->right()); 1369 const Register right = ToRegister(instr->right());
1404 const Register result = ToRegister(instr->result()); 1370 const Register result = ToRegister(instr->result());
1405 1371
1406 // Check for x / 0. 1372 // Check for x / 0.
1407 if (instr->hydrogen_value()->CheckFlag(HValue::kCanBeDivByZero)) { 1373 if (instr->hydrogen_value()->CheckFlag(HValue::kCanBeDivByZero)) {
1408 __ cmp(right, Operand::Zero()); 1374 __ cmp(right, Operand::Zero());
1409 DeoptimizeIf(eq, instr->environment()); 1375 DeoptimizeIf(eq, instr->environment());
1410 } 1376 }
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after
1524 __ b(&done); 1490 __ b(&done);
1525 } 1491 }
1526 } 1492 }
1527 __ bind(&not_kmin_int); 1493 __ bind(&not_kmin_int);
1528 __ mov(dividend, Operand(dividend, ASR, shift)); 1494 __ mov(dividend, Operand(dividend, ASR, shift));
1529 __ bind(&done); 1495 __ bind(&done);
1530 } 1496 }
1531 1497
1532 1498
1533 void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) { 1499 void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) {
1534 Register left = ToRegister(instr->dividend()); 1500 Register dividend = ToRegister(instr->dividend());
1535 Register remainder = ToRegister(instr->temp()); 1501 int32_t divisor = instr->divisor();
1536 Register scratch = scratch0();
1537 Register result = ToRegister(instr->result()); 1502 Register result = ToRegister(instr->result());
1503 ASSERT(!dividend.is(result));
1538 1504
1539 if (!CpuFeatures::IsSupported(SUDIV)) { 1505 if (divisor == 0) {
1540 // If the CPU doesn't support sdiv instruction, we only optimize when we 1506 DeoptimizeIf(al, instr->environment());
1541 // have magic numbers for the divisor. The standard integer division routine 1507 return;
1542 // is usually slower than transitionning to VFP. 1508 }
1543 ASSERT(instr->divisor()->IsConstantOperand());
1544 int32_t divisor = ToInteger32(LConstantOperand::cast(instr->divisor()));
1545 ASSERT(LChunkBuilder::HasMagicNumberForDivisor(divisor));
1546 if (divisor < 0) {
1547 __ cmp(left, Operand::Zero());
1548 DeoptimizeIf(eq, instr->environment());
1549 }
1550 EmitSignedIntegerDivisionByConstant(result,
1551 left,
1552 divisor,
1553 remainder,
1554 scratch,
1555 instr->environment());
1556 // We performed a truncating division. Correct the result if necessary.
1557 __ cmp(remainder, Operand::Zero());
1558 __ teq(remainder, Operand(divisor), ne);
1559 __ sub(result, result, Operand(1), LeaveCC, mi);
1560 } else {
1561 CpuFeatureScope scope(masm(), SUDIV);
1562 // TODO(svenpanne) We *statically* know the divisor, use that fact!
1563 Register right = ToRegister(instr->divisor());
1564 1509
1565 // Check for x / 0. 1510 // Check for (0 / -x) that will produce negative zero.
1566 __ cmp(right, Operand::Zero()); 1511 HMathFloorOfDiv* hdiv = instr->hydrogen();
1512 if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) &&
1513 hdiv->left()->RangeCanInclude(0) && divisor < 0) {
1514 __ cmp(dividend, Operand::Zero());
1567 DeoptimizeIf(eq, instr->environment()); 1515 DeoptimizeIf(eq, instr->environment());
1516 }
1568 1517
1569 // Check for (kMinInt / -1). 1518 __ FlooringDiv(result, dividend, divisor);
1570 if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
1571 __ cmp(left, Operand(kMinInt));
1572 __ cmp(right, Operand(-1), eq);
1573 DeoptimizeIf(eq, instr->environment());
1574 }
1575
1576 // Check for (0 / -x) that will produce negative zero.
1577 if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
1578 __ cmp(right, Operand::Zero());
1579 __ cmp(left, Operand::Zero(), mi);
1580 // "right" can't be null because the code would have already been
1581 // deoptimized. The Z flag is set only if (right < 0) and (left == 0).
1582 // In this case we need to deoptimize to produce a -0.
1583 DeoptimizeIf(eq, instr->environment());
1584 }
1585
1586 Label done;
1587 __ sdiv(result, left, right);
1588 // If both operands have the same sign then we are done.
1589 __ eor(remainder, left, Operand(right), SetCC);
1590 __ b(pl, &done);
1591
1592 // Check if the result needs to be corrected.
1593 __ mls(remainder, result, right, left);
1594 __ cmp(remainder, Operand::Zero());
1595 __ sub(result, result, Operand(1), LeaveCC, ne);
1596
1597 __ bind(&done);
1598 }
1599 } 1519 }
1600 1520
1601 1521
1602 void LCodeGen::DoMulI(LMulI* instr) { 1522 void LCodeGen::DoMulI(LMulI* instr) {
1603 Register result = ToRegister(instr->result()); 1523 Register result = ToRegister(instr->result());
1604 // Note that result may alias left. 1524 // Note that result may alias left.
1605 Register left = ToRegister(instr->left()); 1525 Register left = ToRegister(instr->left());
1606 LOperand* right_op = instr->right(); 1526 LOperand* right_op = instr->right();
1607 1527
1608 bool bailout_on_minus_zero = 1528 bool bailout_on_minus_zero =
(...skipping 4193 matching lines...) Expand 10 before | Expand all | Expand 10 after
5802 __ sub(scratch, result, Operand::PointerOffsetFromSmiKey(index)); 5722 __ sub(scratch, result, Operand::PointerOffsetFromSmiKey(index));
5803 __ ldr(result, FieldMemOperand(scratch, 5723 __ ldr(result, FieldMemOperand(scratch,
5804 FixedArray::kHeaderSize - kPointerSize)); 5724 FixedArray::kHeaderSize - kPointerSize));
5805 __ bind(&done); 5725 __ bind(&done);
5806 } 5726 }
5807 5727
5808 5728
5809 #undef __ 5729 #undef __
5810 5730
5811 } } // namespace v8::internal 5731 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/arm/lithium-codegen-arm.h ('k') | src/arm/macro-assembler-arm.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698