OLD | NEW |
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 1003 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1014 PostorderProcessor* child_; | 1014 PostorderProcessor* child_; |
1015 HLoopInformation* loop_; | 1015 HLoopInformation* loop_; |
1016 HBasicBlock* block_; | 1016 HBasicBlock* block_; |
1017 HBasicBlock* loop_header_; | 1017 HBasicBlock* loop_header_; |
1018 int loop_index; | 1018 int loop_index; |
1019 int loop_length; | 1019 int loop_length; |
1020 HSuccessorIterator successor_iterator; | 1020 HSuccessorIterator successor_iterator; |
1021 }; | 1021 }; |
1022 | 1022 |
1023 | 1023 |
| 1024 // Help with TryRotate pattern matching by checking if sub is 32 - s. It's okay |
| 1025 // if the right operand of sub isn't the same HValue as s if both are HChange |
| 1026 // instructions from the same value. This is called twice to determine whether |
| 1027 // we do a left or right rotation. |
| 1028 static bool TryMatchShiftAmountForRotate(HValue* s, HValue* sub) { |
| 1029 if (!sub->IsSub()) |
| 1030 return false; |
| 1031 HValue* subl = HSub::cast(sub)->left(); |
| 1032 HValue* subr = HSub::cast(sub)->right(); |
| 1033 return subl->representation().IsInteger32() && |
| 1034 subl->IsConstant() && |
| 1035 HConstant::cast(subl)->Integer32Value() == 32 && |
| 1036 (s == subr || |
| 1037 (subr->IsChange() && s->IsChange() && |
| 1038 subr->OperandAt(0) == s->OperandAt(0))); |
| 1039 } |
| 1040 |
| 1041 |
| 1042 // Attempt to replace one of the following patterns with a rotate instruction: |
| 1043 // n << s | n >>> (32 - s) ==> rotate left |
| 1044 // n >>> s | n << (32 - s) ==> rotate right |
| 1045 bool HGraph::TryRotate(HInstruction* instr) { |
| 1046 HBitwise* bor = HBitwise::cast(instr); |
| 1047 ASSERT(bor->op() == Token::BIT_OR); |
| 1048 HShl* shl; |
| 1049 HShr* shr; |
| 1050 if (bor->left()->IsShl() && bor->right()->IsShr()) { |
| 1051 shl = HShl::cast(bor->left()); |
| 1052 shr = HShr::cast(bor->right()); |
| 1053 } else if (bor->left()->IsShr() && bor->right()->IsShl()) { |
| 1054 shl = HShl::cast(bor->right()); |
| 1055 shr = HShr::cast(bor->left()); |
| 1056 } else { |
| 1057 return false; |
| 1058 } |
| 1059 |
| 1060 // Neither shift can be used elsewhere (or it is not safe to delete them). |
| 1061 // Also, both must have Integer32 representation, since we can't rotate |
| 1062 // anything else quickly. |
| 1063 if (shl->UseCount() > 1 || !shl->representation().IsInteger32() || |
| 1064 shr->UseCount() > 1 || !shr->representation().IsInteger32() || |
| 1065 !shr->right()->representation().IsInteger32() || |
| 1066 !shr->left()->representation().IsInteger32() || |
| 1067 !shl->right()->representation().IsInteger32() || |
| 1068 !shl->left()->representation().IsInteger32()) { |
| 1069 return false; |
| 1070 } |
| 1071 |
| 1072 // The value being shifted must be the same. |
| 1073 if (shl->left() != shr->left()) |
| 1074 return false; |
| 1075 HValue* number = shl->left(); |
| 1076 |
| 1077 // The shift values must be s and 32-s. Whether we have found a left or |
| 1078 // right rotate depends on which shift has 32-s. Note that it's okay if the |
| 1079 // "s" values on both sides are distinct HChange instructions, as long as |
| 1080 // their operands are the same value. |
| 1081 HValue* shift_amount = NULL; |
| 1082 if (TryMatchShiftAmountForRotate(shl->right(), shr->right()) | |
| 1083 TryMatchShiftAmountForRotate(shr->right(), shl->right())) { |
| 1084 shift_amount = shr->right(); |
| 1085 } else { |
| 1086 return false; |
| 1087 } |
| 1088 |
| 1089 // We have matched all the operands. Do the replacement. |
| 1090 HRor* ror = new(zone()) HRor(shr->context(), number, shift_amount); |
| 1091 ror->InsertAfter(bor); |
| 1092 bor->DeleteAndReplaceWith(ror); |
| 1093 shl->DeleteAndReplaceWith(NULL); |
| 1094 shr->DeleteAndReplaceWith(NULL); |
| 1095 |
| 1096 return true; |
| 1097 } |
| 1098 |
| 1099 |
| 1100 void HGraph::ReplaceWithRor() { |
| 1101 if (!FLAG_use_replace_with_ror) return; |
| 1102 HPhase phase("H_Replace with ror", this); |
| 1103 for (int i = 0; i < blocks()->length(); ++i) { |
| 1104 HInstruction* instr = blocks()->at(i)->first(); |
| 1105 while (instr != NULL) { |
| 1106 if (instr->IsBitwise() && |
| 1107 HBitwise::cast(instr)->op() == Token::BIT_OR) { |
| 1108 TryRotate(instr); |
| 1109 } |
| 1110 instr = instr->next(); |
| 1111 } |
| 1112 } |
| 1113 } |
| 1114 |
| 1115 |
1024 void HGraph::OrderBlocks() { | 1116 void HGraph::OrderBlocks() { |
1025 HPhase phase("H_Block ordering"); | 1117 HPhase phase("H_Block ordering"); |
1026 BitVector visited(blocks_.length(), zone()); | 1118 BitVector visited(blocks_.length(), zone()); |
1027 | 1119 |
1028 ZoneList<HBasicBlock*> reverse_result(8, zone()); | 1120 ZoneList<HBasicBlock*> reverse_result(8, zone()); |
1029 HBasicBlock* start = blocks_[0]; | 1121 HBasicBlock* start = blocks_[0]; |
1030 PostorderProcessor* postorder = | 1122 PostorderProcessor* postorder = |
1031 PostorderProcessor::CreateEntryProcessor(zone(), start, &visited); | 1123 PostorderProcessor::CreateEntryProcessor(zone(), start, &visited); |
1032 while (postorder != NULL) { | 1124 while (postorder != NULL) { |
1033 postorder = postorder->PerformStep(zone(), &visited, &reverse_result); | 1125 postorder = postorder->PerformStep(zone(), &visited, &reverse_result); |
(...skipping 2361 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3395 if (FLAG_use_range) { | 3487 if (FLAG_use_range) { |
3396 HRangeAnalysis rangeAnalysis(this); | 3488 HRangeAnalysis rangeAnalysis(this); |
3397 rangeAnalysis.Analyze(); | 3489 rangeAnalysis.Analyze(); |
3398 } | 3490 } |
3399 ComputeMinusZeroChecks(); | 3491 ComputeMinusZeroChecks(); |
3400 | 3492 |
3401 // Eliminate redundant stack checks on backwards branches. | 3493 // Eliminate redundant stack checks on backwards branches. |
3402 HStackCheckEliminator sce(this); | 3494 HStackCheckEliminator sce(this); |
3403 sce.Process(); | 3495 sce.Process(); |
3404 | 3496 |
| 3497 #if defined(V8_TARGET_ARCH_ARM) |
| 3498 // TODO: support rotate instructions on other architectures. For now they are |
| 3499 // only supported on ARM. |
| 3500 ReplaceWithRor(); |
| 3501 #endif |
| 3502 |
3405 EliminateRedundantBoundsChecks(); | 3503 EliminateRedundantBoundsChecks(); |
3406 DehoistSimpleArrayIndexComputations(); | 3504 DehoistSimpleArrayIndexComputations(); |
3407 | 3505 |
3408 return true; | 3506 return true; |
3409 } | 3507 } |
3410 | 3508 |
3411 | 3509 |
3412 // We try to "factor up" HBoundsCheck instructions towards the root of the | 3510 // We try to "factor up" HBoundsCheck instructions towards the root of the |
3413 // dominator tree. | 3511 // dominator tree. |
3414 // For now we handle checks where the index is like "exp + int32value". | 3512 // For now we handle checks where the index is like "exp + int32value". |
(...skipping 6568 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
9983 } | 10081 } |
9984 } | 10082 } |
9985 | 10083 |
9986 #ifdef DEBUG | 10084 #ifdef DEBUG |
9987 if (graph_ != NULL) graph_->Verify(false); // No full verify. | 10085 if (graph_ != NULL) graph_->Verify(false); // No full verify. |
9988 if (allocator_ != NULL) allocator_->Verify(); | 10086 if (allocator_ != NULL) allocator_->Verify(); |
9989 #endif | 10087 #endif |
9990 } | 10088 } |
9991 | 10089 |
9992 } } // namespace v8::internal | 10090 } } // namespace v8::internal |
OLD | NEW |